Estimating Causal Effects in Networks with Cluster-Based Bandits
Ahmed Sayeed Faruk, Jason Sulskis, Elena Zheleva · 2025
Read Estimating Causal Effects in Networks with Cluster-Based Bandits by Ahmed Sayeed Faruk, Jason Sulskis, Elena Zheleva (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04200.txt.
Introduction
Ahmed Faruk and co-authors design experiments for networks where people sway each other. The classic A/B test assumes each person's outcome is theirs alone. In social networks that fails, since treated users spill effects onto friends. Fixed tests also waste users on a losing arm for the whole run.
Their bandit methods assign treatment by clusters of the network, not by lone users. The split cuts spillover between arms. Over time the methods shift users toward the better arm while still learning the total effect. On made up network data with built in spillover, cluster bandits beat cluster fixed tests on reward, with little loss in effect accuracy.
Catalog record
| CREATOR | Ahmed Sayeed Faruk, Jason Sulskis, Elena Zheleva |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04200
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Estimating Causal Effects in Networks with Cluster-Based Bandits Ahmed Sayeed Faruk, Jason Sulskis, Elena Zheleva Abstract The gold standard for estimating causal effects is randomized controlled trial (RCT) or A/B testing where a random group of individuals from a population of interest are given treatment and the outcome is compared to a random group of individuals from the same population. However, A/B testing is challenging in the presence of interference, commonly occurring in social networks, where individuals can impact each others outcome. Moreover, A/B testing can incur a high performance loss when one of the treatment arms has a poor performance and the test continues to treat individuals with it. Therefore, it is important to design a strategy that can adapt over time and efficiently learn the total treatment effect in the network. We introduce two cluster-based multi-armed bandit (MAB) algorithms to gradually estimate the total treatment effect in a network while maximizing the expected reward by making a tradeoff between exploration and exploitation. We compare the performance of our MAB algorithms with a vanilla MAB algorithm that ignores clusters and the corresponding RCT methods on semi-synthetic data with simulated interference. The vanilla MAB algorithm shows higher reward-action ratio at the cost of higher treatment effect error due to undesired spillover. The cluster-based MAB algorithms show higher reward-action ratio compared to their corresponding RCT methods without sacrificing much accuracy in treatment effect estimation. Introduction Randomized controlled trials, also known as A/B testing, are widely considered the ”gold standard” in causal inference for measuring the effect of changes. They offer a systematic framework to discover the best treatment effect implementation through estimation of the average treatment effect. Many different treatments are tested through A/B experiments, where one class of users are placed into a treatment group and another class of users are placed into a control group. Technology companies like Google and Facebook run thousands of A/B tests every year in order to make data-driven decisions to improve how they deliver services to their customer base. A typical A/B experiment relies on the Stable Unit Treatment Value Assumption (SUTVA), or that the response of an individual sample depends only on its own assignment to a particular treatment group. SUTVA states that every individual’s outcome is affected only by their own treatment and not by the treatment of any other individual ( Imbens and Rubin 2015 ) . This assumption, however, falls apart when individuals interact with each other, leading to spillover effects. The problem of spillover the treatment from a treated node to a control node through a shared network edge (e.g., information flowing from person to person in an online social network, and diseases spreading between people interacting in the same physical space) leads to interference, which violates SUTVA and thus results in inaccurate treatment effect estimation ( Halloran and Hudgens 2016 ) . An important estimand of interest in networks is the total treatment effect (TTE) which aims to estimate the difference in outcomes in two alternative worlds, one in which everyone is treated and one in which everyone is not treated. For example, we may be interested in comparing a world in which everyone is vaccinated and a world in which no one is vaccinated. Or we may be interested to compare a world in which everyone sees results from the same news feed algorithm versus a world in which everyone sees an alternative news feed algorithm. In both of these worlds interference is allowed. However, due to the fundamental problem of causal inference, estimating this difference directly is impossible. A prominent RCT design for estimating TTE is cluster-based randomization which separated a network into clusters that densely connected within and sparsely connected across ( Ugander et al. 2013 ; Fatemi and Zheleva 2020a ) . Then it assigns treatment and control randomly based on the clusters, keeping interference within clusters but minimizing potential interference across clusters. However, estimating TTE via cluster-based A/B testing can incur a high performance loss when one of the treatment arms has a poor performance and the test continues to treat individuals with it. Reinforcement learning (RL), on the other hand, is a class of methods that learn from sequences of actions to optimize long-term reward in a Markov Decision Process through exploration of states given specific actions. The Multi-armed Bandit (MAB) problem is a classic problem in this paradigm, where a limited set of resources must be allocated between alternative choices in a way that maximizes overall expected rewards. In contrast to A/B testing, high-performing arms are rewarded with more traffic, whereas under-performing arms are punished with less traffic throughout the MAB experiment. The main advantage of MAB experiment over A/B testing is that it requires much smaller sample and thus terminates earlier, but at the cost of a larger false positive rate due to the uneven distribution of samples. MAB can be a good fit with proper exploration-exploitation trade-off in very large networks, where A/B test is expensive in estimating causal effect of interest. Here, we study the use of multi-armed bandits in cluster-based randomization as a more robust and optimal way for learning the total treatment effect in networks. Our target is to estimate the TTE error and reward-action ratio using two-arm bandit network experiments. We propose two cluster-based and one node-based bandit algorithms for network experiments. All these MAB algorithms aim to assign the best performing arm to the newly arrived nodes, but the cluster-based and CMatch-based MAB algorithms also consider the clusters in the network when assigning an arm. The goal of our work is to evaluate and compare the performance of our MAB experiment designs with the corresponding A/B experiments. We also aim to show that exploring a subset of the original network may suffice to learn the total treatment effect with a better reward-action ratio. Related Work Lattimore et. al. have shown that MAB algorithms can be directly applicable to online learning scenarios that involve causal inference, such as exploring treatment effects ( Lattimore, Lattimore, and Reid 2016 ) . A noble non-parametric MAB based exploration algorithm for partially observed incomplete networks has been introduced by Madhawa and Murata ( Madhawa and Murata 2019 ) . Sliding window UCB algorithm has been proposed by Garivier and Moulines which considers the most recent observation to address the issue of non-stationarity in the environment ( Garivier and Moulines 2011 ) . Bootstrap Thompson sampling method can be computationally efficient in large scale bandit problems to optimize exploration-exploitation trade-off in RL ( Eckles and Kaptein 2014 ) . Lihong et. al. formulates a feature-based exploration/exploitation problem as a contextual bandit problem where a learning algorithm sequentially selects articles to serve users based on contextual information about the users and articles and adapting its article-selection strategy based on the feedback to maximize total rewards ( Li et al. 2010 ) . In case of uncertainty, the upper confidence bound (UCB) algorithm follows the principle of optimism which implies that we should optimistically assume an action as correct when we are uncertain about that action. The uncertainty in the estimates is represented by the confidence interval. The actual value of an action is near to the estimated value when the confidence