Dueling Bandits with Constant Regret Bound Using Causal Intervention

The causal dueling bandit problem is to solve the following task: given a causal graph with an unknown distribution where the reward variable is implicit, in each round, there are two actions (interventions) to be taken independently to the graph and the learner subsequently observe the outcome of the preference of the two actions though reward is unobservable. The goal is to minimize regret of the interventions. We propose a new framework for causal dueling bandits that can efficiently utilize relative feedback. In our framework, the learner updates the upper confidence bound using causal knowledge, and applies a UCB-based dueling algorithm to select arms for comparison. We propose two algorithms, Causal Relative Upper Confidence Bound (C-RUCB) and Causal Max Informative Pair (C-MaxInP), which proved to enjoy constant high probability regret and expected cumulative regret in terms of the instance parameters. We empirically demonstrate that our algorithm outperforms other baselines on synthetic data.