Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach

The past decade has seen the rapid development of contextual bandit as a legit framework to model interactive decision-making scenarios, such as personalized recommendation (Li et al. 2010), online advertising (Tang et al. 2013; Avadhanula et al. 2021), and anomaly detection (Ding, Li, and Liu 2019). The key challenge in a contextual bandit problem is to select the most beneficial item (i.e. the corresponding arm or intervention) according to the observed context at each round. In practice it is common that the agent has additional access to logged data from various sources, which may provide some useful information. A key issue is how to accurately leverage offline data such that it can efficiently assist the online decision-making process. However, one inevitable problem is that there may exist compound biases in the offline dataset, probably due to the data collection process, the existence of unobserved variables, the policies implemented by the agent, and so on (Chen et al. 2023). As a consequence, blindly fitting a model without considering those biases will lead to an inaccurate estimator of the reward distribution for each arm, ending up inducing a negative impact on the online learning phase.

To overcome this limitation and make good use of the offline data for online bandit learning, we formulate our framework from a causal inference perspective. Causal inference provides a family of methods to infer the effects of actions from a combination of data and qualitative assumptions about the underlying mechanism. Based on Pearl’s structural causal model (Pearl 2009) we can derive a truncated factorization formula that expresses the target causal quantity with probability distributions from the data. Appropriately adopting that prior knowledge on the reward distribution of each arm can accelerate the learning speed and achieve lower cumulative regret for online bandit algorithms.

Previous studies along this direction (Zhang and Bareinboim 2017; Sharma et al. 2020; Tennenholtz et al. 2021) only focused on one specific bias and have not dealt with compound biases in the offline data. It was shown in (Bareinboim, Tian, and Pearl 2014) that biases could be classified into confounding bias and selection bias based on the causal structure they imply. Due to the orthogonality of confounding and selection bias, simply deconfounding and estimating causal effects in the presence of selection bias using observational data is in general impractical without further assumptions, such as strong graphical conditions (Correa and Bareinboim 2017) or the accessibility of external unbiasedly measured data (Bareinboim and Tian 2015). In this paper, we address this limitation by non-parametrically bounding the target conditional causal effect when confounding and selection biases can not be mitigated simultaneously. We propose two novel strategies to extract prior causal bounds for the reward distribution of each arm and use them to effectively guide the bandit agent to learn a nearly-optimal decision policy. We demonstrate that our approach could further reduce cumulative regret and is resistant to different levels of compound biases in offline data.

Our contributions can be summarized into three parts: 1) We derive causal bounds for conditional causal effects under confounding and selection biases based on c-component factorization and substitute intervention methods; 2) we propose a novel framework that leverages the prior causal bound obtained from biased offline data to guide the arm-picking process in bandit algorithms, thus robustly decreasing the exploration of sub-optimal arms and reducing the cumulative regret; and 3) we develop one contextual bandit algorithm (LinUCB-PCB) and one non-contextual bandit algorithm (UCB-PCB) that are enhanced with prior causal bounds. We theoretically show under mild conditions both bandit algorithms achieve lower regret than their non-causal counterparts. We also conduct an empirical evaluation to demonstrate the effectiveness of our method under the linear contextual bandit setting.

Our work is based on Pearl’s structural causal model (Pearl 2009) which describes the causal mechanisms of a system as a set of structural equations.

Quantitatively measuring causal effects is facilitated with the $do$-operator (Pearl 2009), which simulates the physical interventions that force some variables to take certain values. Formally, the intervention that sets the value of $X$ to $x$ is denoted by $do(x)$. In a SCM, intervention $do(x)$ is defined as the substitution of equation $x=f_{X}(Pa(X),\mathbf{u}_{X})$ with constant $X=x$. The causal model $\mathcal{M}$ is associated with a causal graph $\mathcal{G}=\langle\mathcal{V},\mathcal{E}\rangle$. Each node of $\mathcal{V}$ corresponds to a variable of $\mathbf{V}$ in $\mathcal{M}$. Each edge in $\mathcal{E}$, denoted by a directed arrow $\rightarrow$, points from a node $X\in\mathbf{U}\cup\mathbf{V}$ to a different node $Y\in\mathbf{V}$ if $f_{Y}$ uses values of $X$ as input. The intervention that sets the value of a set of variables $\mathbf{X}$ to $\mathbf{x}$ is denoted by $do(\mathbf{X}=\mathbf{x})$. The post-intervention distribution of the outcome variables $P(\mathbf{y}|do(\mathbf{x}))$ can be computed by the truncated factorization formula (Pearl 2009),

where $\delta_{\mathbf{X}=\mathbf{x}}$ means assigning attributes in $\mathbf{X}$ involved in the term ahead with the corresponding values in $\mathbf{x}$. The post intervention distribution $P(\mathbf{y}|do(\mathbf{x}))$ is identifiable if it can be uniquely computed from observational distributions $P(\mathbf{V})$.

Instead of identifying causal effect in presence of selection bias by adjustment, (Correa, Tian, and Bareinboim 2019) proposed a parallel procedure to justify whether a causal quantity is identifiable and recoverable from selection bias using axiomatical c-components factorization (Tian and Pearl 2002). However, both techniques require strong graphical condition to obtain the unbiased estimation of the true conditional causal effect when both confounding and selection biases exist.

Basically, c-component factorization first partitions nodes in $\mathcal{G}$ into a set of c-components, then expresses the target intervention in terms of the c-factors corresponding to each c-component. Specifically, a c-component $\bm{C}$ denotes a subset of variables in $\mathcal{G}$ such that any two nodes in $\bm{C}$ are connected by a path entirely consisting of bi-directed edges. A bi-directed edge indicates there exists unobserved confounder(s) between the two connected nodes. A c-factor $Q[\bm{C}](\mathbf{v})$ is a function that demonstrates the post-intervention distribution of $\bm{C}$ after conducting interventions on the remaining variables $\mathbf{V}\backslash\bm{C}$ and is defined as

where $Pa(v)$ and $\mathbf{u}_{v}$ denote the set of observed and unobserved parents for node $V$. We explicitly denote $Q[\bm{C}](\mathbf{v})$ as $Q[\bm{C}]$ and list the factorization formula.

(Bareinboim, Tian, and Pearl 2014) showed that $P(\mathbf{y}|do(\mathbf{x}))$ is recoverable and could be computed by Equation 4 if each factor $Q[\bm{C}_{i}]$ is recoverable from the observational data. Accordingly, they developed the RC algorithm to determine the recoverability of each c-factor.

An overview of our framework is illustrated in Figure 1. Our algorithm framework leverages the observational data to derive a prior causal bound for each arm to mitigate the cold start issue in online bandit learning, thus reducing the cumulative regret. In the offline evaluation phase, we call our bounding conditional causal effect (BCE) algorithm (shown in Algorithm 1) to obtain the prior causal bound for each arm given a user’s profile. Then in the online bandit phase, we apply adapted contextual bandit algorithms with the prior causal bounds as input.

Let $\mathbf{C}\in\mathcal{C}$ denote the context vector, where $\mathcal{C}$ denotes the domain space of $\mathbf{C}$. We use $Y$ to denote the reward variable and $\mathbf{X}\in\mathcal{X}$ to denote the intervention variables. At each time $t\in[T]$, a user arrives and the user profile $\mathbf{c}_{t}$ is revealed to the agent. The agent pulls an arm $a_{t}$ with features $\mathbf{x}_{a_{t}}$ based on previous observations. The agent then receives the reward $Y_{t}$ and observes values for all non-intervened variables. We define the the expected mean reward of pulling an arm $a$ with with feature value $\mathbf{x}_{a}$ given user context $\mathbf{c}$ as the conditional causal effect shown below:

When the offline data are available, we can leverage them as prior estimators of the reward for each arm to reduce explorations in the online phase. However, under the circumstances that the causal effect is either unidentifiable or nonrecoverable from the observational data, blindly using the observational data might even have a negative effect on the online learning phase. Our approach is to derive a causal bound for the desired causal effect from the biased observational data. We will further show even when the observational data could only lead to loose causal bounds, we can still guarantee our approach is no worse than conventional bandit algorithms.

In this section, we focus on bounding the effects of conditional interventions in the presence of confounding and sample selection biases. To tackle the identifiability issue of a conditional intervention $P(Y=y|do(\mathbf{x}),\mathbf{c})$, the cond-identify algorithm (Tian 2004) provides a complete procedure to compute conditional causal effects using observational distributions.

where $P_{\mathbf{x}}(y|\mathbf{c})$ is the abbreviated form of the conditional causal effect $P(Y=y|do(\mathbf{x}),\mathbf{c})$. (Tian 2004) showed that if the numerator $P_{\mathbf{x}}(y,\mathbf{c})$ is identifiable, then $P_{\mathbf{x}}(y|\mathbf{c})$ is also identifiable. In the contextual bandit setting, because none of the variables in $\mathbf{C}$ is a descendant of variables in $\mathbf{X}$, the denominator $P_{\mathbf{x}}(\mathbf{c})$ can be reduced to $P(\mathbf{c})$ following the causal topology. Since $P(\mathbf{c})$ is always identifiable and can be accurately estimated, we do not need to consider the situation where neither $P_{\mathbf{x}}(y,\mathbf{c})$ nor $P_{\mathbf{x}}(\mathbf{c})$ is identifiable but $P_{\mathbf{x}}(y|\mathbf{c})$ is still identifiable. Thus the conditional causal effect $P_{\mathbf{x}}(y|\mathbf{c})$ in Equation 6 is identifiable if and only if $P_{\mathbf{x}}(y,\mathbf{c})$ is identifiable. However, the cond-identify algorithm (Tian 2004) is not applicable for the scenario with the presence of selection bias.

Algorithm 1 shows our algorithm framework of bounding conditional causal effects under confounding and selection biases. We develop two methods, c-component factorization and substitute intervention, and apply each to derive a bound for conditional causal effect separately. We then compare the two causal bounds and return the tighter upper/lower bound. Specifically, lines 5-10 in Algorithm 1 decompose the target causal effect following c-component factorization and recursively call our RC* algorithm (shown in Algorithm 2) to bound each c-factor. Lines 11-15 search over recoverable intervention space and find valid substitute interventions to bound the target causal effect. Lines 16-18 compare two derived causal bounds and take the tighter upper/lower bound as the output causal bounds. We also include discussions regarding the assumptions on causal graph in Appendix.

In this section we show how to incorporate our derived causal bounds to online contextual bandit algorithms. We focus on the stochastic contextual bandit setting with linear reward function. We define the concatenation of user and arm feature as $\mathbf{x}_{\mathbf{c}_{t},a}=[\mathbf{c}_{t},\mathbf{x}_{a}]\in\mathbb{R}^{d}$ when the agent picks arm $a$ based on user profile $\mathbf{c}_{t}$ at time $t\in[T]$ and use its simplified notion $\mathbf{x}_{t,a}$ to be consistent with previous work like LinUCB. Under the linear assumption, the binary reward is generated by a Bernoulli distribution $Y_{a}\sim Ber(\langle\bm{\theta},\mathbf{x}_{t,a}\rangle)$ parameterized by $\bm{\theta}$. Let $a_{t}=\operatorname*{arg\,max}_{a\in\mathcal{A}}\mathbb{E}[Y_{a}]$, the expected cumulative regret up to time $T$ is defined as:

At each round the agent pulls an arm based on the user context, observes the reward, and aims to minimize the expected cumulative regret $\mathbb{E}[R(T)]$ after $T$ rounds. We next conduct regret analysis and show our strategy could consistently reduce the long-term regret with the guide of a prior causal bound for each arm’s reward distribution.

In this section, we conduct experiments to validate our proposed methods. We use the synthetic data generated following the graph structure in Figure 2. We generate 30000 data points following the conditional probability table in Appendix to simulate the confounded and selection biased setting. After conducting the preferential exclusion indicated by the selection mechanism, there are approximately 15000 data points used for offline evaluation.

This work studies bounding conditional causal effects in the presence of confounding and sample selection biases using causal inference techniques and utilizes the derived bounds to robustly improve online bandit algorithms. We present two novel techniques to derive causal bounds for conditional causal effects given offline data with compound biases. We develop contextual and non-contextual bandit algorithms that leverage the derived causal bounds and conduct their regret analysis. Theoretical analysis and empirical evaluation demonstrate the improved regrets of our algorithms. In future work, we will study incorporating causal bounds into advanced bandit algorithms such as state-of-the-art linear contextual bandits (Hao, Lattimore, and Szepesvari 2020), contextual bandits under non-linearity assumption (Zhou, Li, and Gu 2020), and bandits with adversarial feedback (Luo et al. 2023), to comprehensively demonstrate the generalization ability of our approach.

This work was supported in part by NSF under grants 1910284, 1940093, 1946391, 2137335, and 2147375.

Our research could benefit online recommendation system providers so that they can mitigate biases from multiple sources while conducting recommendations. Our research could also benefit users of online recommendation systems as we aim to eliminate the influence of biases and achieve accurate personalized recommendation. Since fairness could be regarded as a certain type of bias, our research could be further extended to prevent users from receiving biased recommendations, especially for those from disadvantaged groups. To the best knowledge, we do not see any negative ethical impact from our paper.