Off-Policy Evaluation Using Information Borrowing and Context-Based Switching

Contextual bandits framework finds a wide range of applications such as recommendations systems (Li et al.,, 2011), personalized healthcare (Zhou et al.,, 2017), advertising (Bottou et al.,, 2013), and education (Mandel et al.,, 2014). In contextual bandits, a decision maker (often an algorithm) observes a context and takes an action according to a policy and observes a reward. For a recommendation algorithm, the context can be the information about the user and the history is his past online clicks/purchases, and a reward is obtained when he clicks/buys the item. Importantly, the algorithm can only observe the reward for the selected actions, and not for the others. The goal is to maximize the expected reward by choosing the best policy out of a set of candidate policies. A natural approach towards that end is to evaluate the candidate policies by calculating their expected reward, called policy evaluation, and then choose the policy with the highest expected reward. We consider the fundamental problem of off-policy evaluation (OPE) in contextual bandits, where one uses the data gathered by a past policy, known as the logging policy, to estimate the expected reward of a new policy, known as the target policy. OPE eliminates the cost of performing policy evaluation via online experiments, and avoids the risks of exposing subjects to untested policies.

There are three main approaches to address the OPE problem: $(i)$ Direct Method (DM) first gets an estimate of the reward model and uses it to estimate the value of the target policy. DM often has low variance. However, its bias can be significant, especially when the true reward model does not belong to the function class used for the reward function estimation. $(ii)$ Inverse Propensity Scoring (IPS) estimator (Horvitz and Thompson,, 1952) uses importance weighting to correct the mismatch between proportions of actions due to the difference between the logging and target polices. While the IPS estimator is unbiased, its variance can be really large due to large importance weights. $(iii)$ Doubly Robust (DR) estimator (Robins and Rotnitzky,, 1995; Bang and Robins,, 2005; Dudík et al.,, 2011, 2014) is a combination of DM and IPS to achieve the low variance of DM and no bias of IPS. While DR is known to be asymptotically optimal under some assumption (Su et al.,, 2020), its finite-sample variance can still be quite high when importance weights are large.

Many recent works focus on reducing the variance of the DR estimator. Wang et al., (2017) introduced a switching approach that switches between using a DM and DR, depending on the importance weights. Su et al., (2020) takes a shrinkage approach where they replace the importance weights by smaller weights which optimizes the mean squared error. The variance of such estimators is usually caused by mismatches in supports of data-collecting policy and target policy. Mou et al., (2023) assume that the reward function lies within a reproducing kernel Hilbert space to address such mismatches. Khan et al., (2024) instead use partial identification methods to address these mismatches. There are however few works addressing the high bias of the DM method. Su et al., (2020) has revealed the importance of choosing an appropriate reward model. Through an extensive study, they have shown that different reward models result in the best estimates in different scenarios. Lichtenberg et al., (2023) use reward clipping approaches for achieving practical less-bias results.

In this work, we propose an innovative approach for the OPE problem, which we call the Doubly Robust with Information borrowing and Context-based switching (DR-IC) estimator. The approach is based on two key proposals for improving the performance of the standard DR estimator.

First, we propose a modified DM that uses an intuitive and widely applicable parametric reward model that can significantly reduce the bias. The fundamental idea of the proposed reward model is borrowing information from ‘similar’ and ‘important’ contexts through a correlation structure. In particular, this reward model assigns more weight to data points that are ‘similar’ to the test data point through the choice of a kernel. The bandwidth of the kernel is chosen adaptively, depending on the importance weight associated with the test data point. We call this new DM as DM with Information Borrowing (DM-IB). We theoretically show that the bias of the DM-IB goes to zero as the number of samples increases. We also empirically demonstrate the advantages of DM-IB.

Second, we propose a context-based switching scheme for adpatively choosing between the DM-IB and the DR estimator (which also uses a reward model with information borrowing). Unlike the switching scheme proposed in Wang et al., (2017) which does switching based on the importance weights, our approach uses the Kullback-Leibler (KL) divergence between the logging policy and target policy, given the context, to do the switching. We call this the DR-IC estimator. Through extensive experiments, we demonstrate the superior performance of our DR-IC estimator compared to the state-of-the-art methods (Wang et al.,, 2017; Farajtabar et al.,, 2018; Su et al.,, 2020) on a number of benchmark problems.

In the contextual bandits problem, the algorithm observes a context $x\in\mathcal{X}$, takes an action $a\in\mathcal{A}$, and gets a scalar reward $r(x,a)$. We assume that the context space $\mathcal{X}\subset\mathbb{R}^{d}$ is continuous and the action space $\mathcal{A}$ is finite. The contexts are sampled i.i.d. according to a distribution $\nu_{C}(\cdot)$. Reward $r(x,a)$ has a distribution conditioned on $(x,a)$ denoted by $\nu_{R}(\cdot|x,a)$. We assume that $\nu_{R}(\cdot|x,a)$ is a Lipschitz function with respect to $x$ for any given $a$, formalizing the intuition that similar context should give similar rewards for the same action. The algorithm selects actions according a decision rule called policy, which maps the observed context to a distribution over the action space. A policy $\pi$ is denoted as a conditional distribution $\pi(a|x)$ which specifies the probability of selecting action $a$ when the context $x$ is observed. The value of a policy $\pi$, denoted as $V^{\pi}$, is defined as

In the following, we will also write $\pi(x,a,r)$ to denote the joint distribution over context-action-reward tuples when actions are selected by the policy $\pi$. i.e., $\pi(x,a,r)=\nu_{C}(x)\pi(a|x)\nu_{R}(r|x,a)$.

In the off-policy evaluation problem, we are given a data set $\mathcal{D}=\{(x_{i},a_{i},r_{i})\}^{n}_{i=1}$ that consists of $n$ i.i.d. samples of context-action-reward tuple generated by a logging policy $\mu$, i.e., $(x_{i},a_{i},r_{i})\sim\mu$. The goal is to estimate the value $V^{\pi}$ of a target policy $\pi$ using this offline dataset $\mathcal{D}$.

There are three standard and well known approaches for off-policy evaluation.

Direct Method: In DM, we train a reward model $\widehat{r}$ as

where $\mathcal{F}$ is a suitable function class. The DM estimator is then given as

Though the DM estimator typically has low variance, it often suffers from large bias (Dudík et al.,, 2011).

Inverse Propensity Scoring Estimator : IPS estimator makes use of the importance weights, defined as $w(x,a):=\frac{\pi(a|x)}{\mu(a|x)}$, to get an unbiased estimate (Horvitz and Thompson,, 1952). The IPS estimator is given as

We make the standard assumption that $\mu(a|x)>0$ whenever $\pi(a|x)>0$, ensuring that $w(x,a)<\infty$. Though the IPS estimator is unbiased, when there is a substantial mismatch between the policies $\mu$ and $\pi$, the importance weights will be large and hence the variance will also be large.

Doubly Robust Estimator: DR approach combines DM and IPS estimator as

where $\widehat{r}$ is as given in (2). DR estimator preserves the unbiased nature of the IPS and hence is robust to a poor reward estimator $\widehat{r}$. At the same time, because the IPS part in the DR estimator is using a shifted reward, the variance of the DR estimator is smaller than that of the IPS estimator. It is known that DR estimator is asymptotically optimal as long the reward estimator is consistent (Su et al.,, 2020). However, its finite-sample variance can be quite high due to large importance weights when the logging policy and the evaluation policy are different.

Recently, different approaches to further reduce the variance of the DR approaches have been studied. The closest to our work is (Wang et al.,, 2017), which proposed a switching approach based on the importance weights. The proposed switch estimator uses the IPS approach when the importance weights are less than a threshold and switches to the DM approach when the importance weights exceeds that threshold. Formally, switch estimator is given as

where $\tau$ is the threshold. The IPS part in the above estimator is can also be replaced by a DR estimator.

In this section, we introduce our new approach, which we call the Doubly Robust with Information borrowing and Context-based switching (DR-IC) estimator. The approach is based on two key proposals for improving the performance of the standard DR estimator. First, we propose a modified DM that uses a innovative reward model which borrows information from similar and important contexts in order to reduce the bias. We call this as DM with Information Borrowing (DM-IB). Second, we propose a context-based switching scheme for adpatively choosing between the DM-IB and the DR (which also uses the information borrowing reward model) for reducing the variance. We call this combined approach the DR-IC estimator.

In this section, we outline our experimental results built on the Open Bandit Pipeline (Saito et al.,, 2020) library. For the choice of datasets, we follow (Dudík et al.,, 2011, 2014; Wang et al.,, 2017; Farajtabar et al.,, 2018; Su et al.,, 2020) to transform the UC Irvine (UCI) multi-class classification datasets (Dua and Graff,, 2017) into off-policy evaluation datasets. The notion of classes in a multi-class dataset becomes the action space in a contextual bandit problem, thus the predicted label becomes the action taken. The classification error becomes the observed loss $l$. Note that this is equivalent to observing a reward $r$, under the transformation $r=1-l$. Specifically, we consider the indicator loss. That is, for a multi-class example $(x,a^{*})$, whenever the rewards are deterministic, then taking an action $a$ yields the reward $r=\mathds{1}\{a=a^{*}\}$, or whenever the rewards are stochastic, then taking an action $a$ yields the reward $r=\mathds{1}\{a=a^{*}\}$ with probability $0.7$ and $r=1-\mathds{1}\{a=a^{*}\}$ otherwise.

We split every dataset into two parts - a training set (70%) and a test set (30%). We generate a context-dependent logging policy based on the training set, and use this logging policy to generate the actions. Towards this end, we generate actions uniformly at random, and train a logistic regression model on this training set with randomized actions. We use this model on the test set to get the predicted action distribution that is used as a logging policy. This logging policy $\mu$ then is used to generate $n$ sized bandit data by sampling a context $x$ from the entire dataset, sampling an action $a\sim\mu(\cdot\mid x)$, and then observing a deterministic or stochastic reward $r$. The value of $n$ varies across different datasets.

We also use this training set to generate an evaluation policy by repeating the procedure of getting a logging policy, with the only difference is that the logistic regression model is trained with the true actions present in the training set. We use this evaluation policy $\pi$ to predict the actions in the testing set, and calculate the expected reward, which forms the ground truth value for the given UCI dataset.

We measure the performance of various estimators with clipped mean squared error (MSE), i.e. $\mathbb{E}[(\widehat{V}^{\pi}-V^{\pi})^{2}\wedge 1]$ where $\widehat{V}^{\pi}$ is the value of the estimator and $V^{\pi}$ is the ground truth. We use $300-500$ replicates of bandit data generation to estimate the MSE and repeat this process for $10-40$ different seeds to generate the bands (which is $\pm 0.5$ the standard deviation) around the estimated MSE.

We compare the MSE of the following estimators. $1.$ DR-IC: our proposed estimator given in (12) with the tuning parameters optimized according to (13), $2.$ DR-IC (oracle): our proposed estimator with the tuning parameter optimized using the actual MSE with respect to the ground truth, $3.$ DR-IC($\tau=0$): this is our proposed $\widehat{V}^{\pi}_{\mathrm{DM\mbox{-}IB}}$ as given in (11), $4.$ DM: as given (3) using traditional ridge regression reward estimate (7), $5.$ DR: standard DR estimator according to (5) using the reward estimate (7), $6.$ MR-DR: More robust Doubly robust estimator based on Farajtabar et al., (2018), $7.$ DR-OS (oracle): the oracle tuned version of the shrinkage based estimator proposed in Su et al., (2020) , $8.$ DR-OS: optimized version of the shrinkage estimator proposed in Su et al., (2020), $9.$ switch-DR (oracle): the oracle version of the switch estimator proposed in Wang et al., (2017), and $10.$ switch-DR : the switch estimator proposed in Wang et al., (2017) with tuning parameters optimized using an estimated MSE. In Appendix D, we include a separate simulation study comparing DR-IC($\tau=0$) with a standard Nadaraya Watson estimator, to highlight the benefits of the specific kernel introduced in our model, in effectively borrowing information.

In Fig 2, we show several attractive properties of the proposed method with respect to the state of the art algorithms. First, in seven out of the eight cases considered, the borrowing of information displays a significant practical improvement as shown in the performance of DR-IC($\tau=0$) (DM-IB) over the standard DM across all sample sizes. In fact, in five out of the eight cases, DR-IC ($\tau=0$) either outperforms or is as good as a traditional DR approach across the different sample sizes.

Second, the proposed context-based switching algorithm improves upon the performance of DR-IC($\tau=0$) and clearly dominates the state-of-the-art methods in seven out of the eight cases considered. The oracle version of the proposed method DR-IC (oracle) significantly outperforms the oracle versions of other methods, while the tuned version DR-IC is either as good as or better than the tuned versions of the competitors. This also highlights the advantages of the KL based switching approach over the importance weight based switching approach of Wang et al., (2017). In five out of the eight cases, DR-IC shows significant improvement over switch-DR, and is as good as switch-DR in the remaining three cases.

Third, the results indicate that for the deterministic reward model, the DR-IC and DR-IC(oracle) are at least as good as, or significantly better than all their counterparts. For the stochastic reward model, the variability increases for all estimators. Nonetheless, DR-IC is still atleast as good as, or better than all the other estimators in three out of four cases.

Additional experiments: We note that we have included more experiment results and details of the implementation in the appendix. In Appendix D, we have provided a comparison of the proposed approach with a kernel based non-parametric reward estimator, and illustrate the advantages of the proposed formulation. We have also included the code in this github page.

In this work, we have introduced the idea of information borrowing which utilizes the similarity structure among context-action pairs and the importance weights associated with the logging and evaluation policies to significantly improve the practical properties of a traditional direct method for OPE. Under assumptions discussed in Section 4, the proposed reward estimator is asymptoticallly unbiased, which is usually not the case for traditional DM reward models. We further introduce a KL divergence based switching algorithm that employs the strengths of information borrowing, resulting in a context-based switch estimator that dominates the state of the art algorithms in most cases. These advantages are relevant not just for the fundamental problem of off-policy evaluation as considered in this article, but for more general problems in off-policy optimization and reinforcement learning as well. The notion of effective information borrowing becomes particularly crucial while assimilating information from multiple context distributions or logging policies with varying similarities to the evaluation policy. These problems indicate exciting possibilities for future research using the idea of effective policy dependent information borrowing introduced in this paper. Another exciting direction of research would be to identify better optimization schemes for the tuning parameter $\tau$ and get the tuned estimate closer to the oracle version.