By incorporating causal inference into bandits, we first propose the d-separation based upper confidence bound bandit algorithm (D-UCB), based on which we then propose the fair causal bandit (F-UCB) for achieving the counterfactual individual fairness. Our work is inspired by recent research on causal bandits [1]}, [2]}, [3]}, [4]}, [5]}, which studied how to learn optimal interventions sequentially by representing the relationship between interventions and outcomes as a causal graph along with associated conditional distributions. For example, [5]} developed the causal UCB (C-UCB) that exploits the causal relationships between the reward and its direct parents.
However, different from previous works, our algorithms adopt soft intervention [7]} to model the arm selection strategy and leverage the d-separation set identified from the underlying causal graph, thus greatly reducing the amount of exploration needed to achieve low cumulative regret. We show that our D-UCB achieves \(\tilde{O}(\sqrt{|\mathbf {W}| \cdot T})\)  regret bound where \(T\)  is the number of iterations and
\(\mathbf {W}\)  is a set that d-separates arm/user features and reward \(R\)  in the causal graph.
As a comparison, the C-UCB achieves \(\tilde{O}(\sqrt{|Pa(R)| \cdot T})\)  where \(Pa(R)\)  is the parental variables of \(R\)  that is a trivial solution of the d-separation set.
In our F-UCB, we further achieve counterfactual fairness in each round of exploration. Counterfactual fairness requires the expected reward an individual would receive keeps the same if the individual's sensitive attribute were changed to its counterpart. The introduced counterfactual reward combines two interventions, a soft intervention on the arm selection and a hard intervention on the sensitive attribute. The F-UCB achieves counterfactual fairness in online recommendation by picking arms from a subset of arms at each round in which all the arms satisfy counterfactual fairness constraint. Our theoretical analysis shows F-UCB achieves \(\tilde{O}(\frac{\sqrt{|\mathbf {W}|T}}{\tau - \Delta _{\pi _0}})\)  cumulative regret bound where \(\tau \)  is the fairness threshold and \(\Delta _{\pi _0}\)  denotes the maximum fairness discrepancy of a safe policy \(\pi _0\) , i.e., a policy that is fair across all rounds.
