Linear Combinatorial Semi-Bandit with Causally Related Rewards

1 Introduction

In the seminal form of the Multi-Armed Bandit (MAB) problem, an agent selects an arm from a given set of arms at sequential rounds of decision-making. Upon selecting an arm, the agent receives a reward, which is drawn from the unknown reward distribution of that arm. The agent aims at maximizing the average reward over the gambling horizon [Robbins, 1952]. The MAB problem portrays the exploration-exploitation dilemma, where the agent decides between accumulating immediate reward and obtaining information that might result in larger reward only in the future

∗Equal Contribution

[Maghsudi and Hossain, 2016]. To measure the performance of a strategy, one uses the notion of regret. It is the difference between the accumulated reward of the applied decisionmaking policy and that of the optimal policy in hindsight.

In a combinatorial semi-bandit setting [Chen et al., 2013], at each round, the agent selects a subset of base arms. This subset is referred to as a super arm. She then observes the individual reward of each base arm that belongs to the selected super arm. Consequently, she accumulates the collective reward associated with the chosen super arm. The combinatorial MAB problem is challenging since the number of super arms is combinatorial in the number of base arms. Thus, conventional MAB algorithms such as [Auer et al., 2002] are not appropriate for combinatorial problems as they result in suboptimal regret bounds. The aforementioned problem becomes significantly more difficult when there are causal dependencies amongst the reward distributions.

In some cases, it is possible to model the causal structure that affects the rewards [Lattimore et al., 2016]. Therefore, exploiting the knowledge of this structure helps to deal with the aforementioned challenges. In our paper, we develop a novel combinatorial semi-bandit framework with causally related rewards, where we rely on Structural Equation Models (SEMs) [Kaplan, 2008] to model the causal relations. At each time of play, we see the instantaneous rewards of the chosen base arms as controlled stimulus to the causal system. Consequently, in our causal system, the solution to the decision-making problem is the choice over the exogenous input that maximizes the collected reward. We propose a decision-making policy to solve the aforementioned problem and prove that it achieves a sublinear regret bound in time. Our developed framework can be used to model various realworld problems, such as network data analysis of biological networks or financial markets. We apply our framework to analyze the development of Covid-19 in Italy. We show that our proposed policy is able to detect the regions that contribute the most to the spread of Covid-19 in the country.

Compared to previous works, our proposed framework does not require any prior knowledge of the structural dependencies. For example, in [Tang et al., 2017], the authors exploit the prior knowledge of statistical structures to learn the best combinatorial strategy. At each decision-making round, the agent receives the reward of the selected super arm and some side rewards from the selected base arms' neighbors. In

[Huyuk and Tekin, 2019] a Combinatorial Thompson Sampling (CTS) algorithm to solve a combinatorial semi-bandit problem with probabilistically triggered arms is proposed. The proposed algorithm has access to an oracle that determines the best decision at each round of play based on the already collected data. Similarly, the authors in [Chen et al., 2016] study a setting where triggering super arms can probabilistically trigger other unchosen arms. They propose an Upper Confidence Bound (UCB)-based algorithm that uses an oracle to improve the decision-making process. In [Yu et al., 2020], the authors formulate a combinatorial bandit problem where the agent has access to an influence diagram that represents the probabilistic dependencies in the system. The authors propose a Thompson sampling algorithm and its approximations to solve the formulated problem. Further, there are some works that study the underlying structure of the problem. For example, in [Toni and Frossard, 2018], the authors attempt to learn the structure of a combinatorial bandit problem. However, they do not assume any causal relations between rewards. Moreover, in [Sen et al., 2017], the MAB framework is employed to identify the best soft intervention on a causal system while it is assumed that the causal graph is only partially unknown.

The rest of the paper is organized as follows. In Section 2, we formulate the structured combinatorial semi-bandit problem with causally related rewards. In Section 3, we introduce our proposed algorithm, namely SEM-UCB. Section 4 includes the theoretical analysis of the regret performance of SEM-UCB. Section 5 is dedicated to numerical evaluation. Section 6 concludes the paper.

2 ProblemFormulation

Let [N] = {1, 2, . . . ,N} denote the set of base arms. bt = [bt[1], bt[2], . . . , bt[N]] ∈ [0, 1]N represents the vector of instantaneous rewards of the base arms at time t. The instantaneous rewards of each base arm i ∈ [N] are independent and identically distributed (i.i.d.) random variables drawn from an unknown probability distribution with mean β[i]. We collect the mean rewards of all the base arms in the mean reward vector of β = [β[1], β[2], . . . , β[N]].

We consider a causally structured combinatorial semibandit problem where an agent sequentially selects a subset of base arms over time. We refer to this subset as the super arm. More precisely, at each time t, the agent selects a decision vector xt = [xt[1], xt[2], . . . , xt[N]] ∈ {0, 1}N . If the agent selects the base arm i at time t, we have xt[i] = 1, otherwise xt[i] = 0. The agent observes the value of bt[i] at time t only if xt[i] = 1. The agent is allowed to select at most s base arms at each time of play. Hence, we define the set of all feasible super arms as

where ∥·∥0 determines the number of non-zero elements in a vector. In our problem, the parameter s is pre-determined and is given to the agent.

We take advantage of a directed graph structure to model the causal relationships in the system. We consider an unknown stationary sparse Directed Acyclic Graph (DAG)

G = (V, E,A), where V denotes the set of N vertices, i.e., |V| = N, E is the edge set, and A denotes the weighted adjacency matrix. By p ≤ N - 1, we denote the length of the largest path in the graph G. We assume that the reward generating processes in the bandit setting follow an error-free Structural Equation Model (SEM) ([Giannakis et al., 2018], [Bazerque et al., 2013]). The exogenous input vector and the endogenous output vector of the SEM at each time t are denoted by zt = [zt[1], zt[2], . . . , zt[N]] and yt = [yt[1], yt[2], . . . , yt[N]], respectively. At each time t, the exogenous input zt represents the semi-bandit feedback in the decision-making problem. Formally,

where diag(·) represents the diagonalization of its given input vector. Consequently, we define the elements of the endogenous output vector yt as

where F is a diagonal matrix that captures the effects of the exogenous input vector zt. The SEM in Equation (3) implies that the output measurement yt[i] depends on the single-hop neighbor measurements in addition to the exogenous input signal zt[i]. In our formulation, at each time t, the endogenous output yt[i] represents the overall reward of the corresponding base arm i ∈ [N]. Therefore, at each time t, the overall reward of each base arm comprises two parts; one part directly results from its instantaneous reward, while the other part reflects the effect of causal influences of other base arms' overall rewards.

In Equation (3), the overall rewards are causally related. Thus, the adjacency matrix A represents the causal relationships between the overall rewards; accordingly, the element A[i, j] of the adjacency matrix A denotes the causal impact of the overall reward of base arm j on the overall reward of base arm i, and we have A[i, i] = 0, ∀i = 1, 2, . . . ,N. We assume that the agent is not aware of the causal relationships between the overall rewards. Hence, the adjacency matrix A is unknown a priori. In the following, we work with the matrix form of Equation (3), defined at time t as

In Figure 1, we illustrate an exemplary network consisting of N vertices and the underlying causal relations. Based on our problem formulation, the agent is able to observe both the exogenous input signal vector zt and the endogenous output signal vector yt. As we see, there does not exist necessarily a causal relation between every pair of nodes.

By inserting (2) in (4) and solving for yt we obtain

Finally, we define the payoff received by the agent upon choosing the decision vector xt as

where 1 is the N-dimensional vector of ones. Since the graph G is a DAG, it implies that with a proper indexing of the vertices, the adjacency matrix A is a strictly upper triangular matrix. This guarantees that the matrix (I -A) is invertible. In our problem, since the agent directly observes the exogenous input, we assume that the effects of F on the exogenous inputs are already integrated in the instantaneous rewards. Therefore, to simplify the notation and without loss of generality, we assume that F = I in the following.

Given a decision vector xt ∈ X, the expected payoff at time t is calculated as

where the expectation is taken with respect to the randomness in the reward generating processes.

Ideally, the agent's goal is to maximize her total mean payoff over a time horizon T. Alternatively, the agent aims at minimizing the expected regret, defined as the difference between the expected accumulated payoff of an oracle that follows the optimal policy and that of the agent that follows the applied policy. Formally, the expected regret is defined as

where x∗ = argmax x∈X µ(x) is the optimal decision vector, and xt denotes the selected decision vector at time t under the applied policy.

Remark 1. The definition of payoff in (6) implies that we are dealing with a linear combinatorial semi-bandit problem with causally related rewards. In general, due to the randomness in selection of the decision vector xt, the consecutive overall reward vectors yt become non-identically distributed. In the following section, we propose our algorithm that is able to deal with such variables. This is an improvement over the previous methods, such as [Chen et al., 2016] and [Huyuk and Tekin, 2019], that are not able to cope with our problem formulation, as they are specially designed to work with i.i.d. random variables.

3 Decision-Making Strategy

In this section, we present our decision-making strategy to solve the problem described in Section 2. Our proposed policy consists of two learning components: (i) an online graph learning and (ii) an Upper Confidence Bound (UCB)-based reward learning. In the following, we describe each component separately and propose our algorithm, namely SEMUCB.

3.1 Online Graph Learning

The payoff defined in (6) implies that the knowledge of A is necessary to select decision vectors that result in higher accumulated payoffs. Therefore, the agent aims at learning the matrix A to improve her decision-making process. To this end, we propose an online graph learning framework that uses the collected feedback, i.e., the collected exogenous input and endogenous output vectors, to estimate the ground truth matrix A. In the following, we formalize the online graph learning framework.

At each time t, we collect the feedback up to the current time in Zt = [z1 . . . zt] and Yt = [y1 . . . yt]. Therefore,

We assume that the right indexing of the vertices is known prior to estimating the ground truth adjacency matrix. We use the collected feedback Yt and Zt as the input to a parametric graph learning algorithm ([Giannakis et al., 2018], [Dong et al., 2019]). More precisely, we use the following optimization problem to estimate the adjacency matrix at time t.

where ∥·∥2 represents the L2 -norm of matrices and g(A) is a regularization function that imposes sparsity over A. In our numerical experiments, we work with different regularization functions to demonstrate the effectiveness of our proposed algorithm in different scenarios. As an example, we impose the sparsity property on the estimated matrix ˆAt in (10) by defining g(A) = λ∥A∥1 , where ∥·∥1 is the L1 -norm of the matrices and λ is the regularization parameter. Our choices of regularization function guarantee that the optimization problem (10) is convex.

3.2 SEM-UCB Algorithm

We propose our decision-making policy in Algorithm 1. The key idea behind our algorithm is that it works with observations for each base arm, rather than the payoff observations for each super arm. As the same base arm can be observed while selecting different super arms, we can use the obtained information from selection of a super arm to improve our payoff estimation of other relevant super arms. This, combined with the fact that our algorithm simultaneously learns the causal relations, significantly improves the performance of our proposed algorithm and speed up the learning process.

For each base arm i, we define the empirical average of instantaneous rewards at time t as

where mt[i] denotes the number of times that the base arm i is observed up to time t. Formally,

Algorithm 1 SEM-UCB: Structural Equation Model-Upper Confidence Bound

Input: Parameter s, initialization matrixM.

• 1: for t = 1, . . . ,N do
• 2: Select column t of the initialization matrix M as the decision vector xt.
• 3: Observe zt and yt.
• 4: end for
• 5: for t = N +1, . . . , T do
• 6: Solve (10) to obtain ˆAt-1.
• 7: Calculate Et-1[i] using (13), ∀i ∈ [N].
• 8: Select decision vector xt that solves (14).
• 9: Observe zt and yt.
• 10: end for

The initialization phase of SEM-UCB algorithm follows a specific strategy to create a rich data that helps to learn the ground truth adjacency matrix. At each time t during the first N times of play, SEM-UCB picks the column t of an uppertriangular initialization matrix M ∈ {0, 1}N×N , where M is created as follows. All diagonal elements of M are equal to 1. As for the column i, if i ≤ s, we set all elements above diagonal to 1. If s + 1 ≤ i ≤ N, we select s - 1 elements above diagonal uniformly at random and set them to 1. The remaining elements are set to 0.

After the initialization period, our proposed algorithm takes two steps at each time t to learn the causal relationships and the expected instantaneous rewards of the base arms. First, it uses the collected feedback Yt and Zt and solves the optimization problem (10) to obtain the estimated adjacency matrix. It then uses the reward observations to calculate the UCB index Et[i] for each base arm i, defined as

Afterward, the algorithm selects a decision vector xt using the current estimate of the adjacency matrix and the developed UCB indices of the base arms. Let Et = [Et[1],Et[2], . . . ,Et[N]]. At time t, SEM-UCB selects xt as

Remark 2. The initialization phase of our algorithm guarantees that all the base arms are pulled at least once and the matrix M is full rank. Consequently, the adjacency matrix A is uniquely identifiable from the collected feedback [Bazerque et al., 2013].

Remark 3. Let c⊤ = 1⊤(I - ˆAt-1)-1 diag(Et-1). Since all the elements of both matrices Et-1 and ˆAt-1 are nonnegative, we have c[i] > 0, ∀i ∈ [N]. Thus, the optimization problem (14) reduces to finding the s-biggest elements of c. Therefore, (14) can be solved efficiently based on the choice of sorting algorithm used to order the elements of c.

The computational complexity of the SEM-UCB algorithm varies depending on the solver that is used to learn the graph. For example, if we use OSQP solver [Stellato et al., 2020], we achieve a computational complexity of order O(N 4 ).

4 Theoretical Analysis

In this section, we prove an upper bound on the expected regret of SEM-UCB algorithm. We use the following definitions in our regret analysis. For any decision vector x ∈ X, let ∆(x) = µ(x∗ ) - µ(x). We define ∆max = max x:µ(x)<µ(x∗ ) ∆(x) and ∆min = min x:µ(x)<µ(x∗ ) ∆(x). Moreover, let w⊤ t = 1⊤(I- ˆAt)-1 diag(xt+1). We define wmax = max t max i wt[i].

The following theorem states an upper bound on the expected regret of SEM-UCB.

Theorem 1. The expected regret of SEM-UCB algorithm is upper bounded as

Proof. See Section 1 of supplementary material.

■

5 Experimental Analysis

In this section, we present experimental results to provide more insight on the usefulness of learning the causal relations for improving the decision-making process. We evaluate the performance of our algorithm on synthetic and realworld datasets by comparing it to standard benchmark algorithms.

Benchmarks. We compare SEM-UCB with state-of-theart combinatorial semi-bandit algorithms that do not learn the causal structure of the problem. Specifically, we compare our algorithm with the following policies: (i) CUCB [Chen et al., 2016] calculates a UCB index for each base arm at each time t and feeds them to an approximation oracle that outputs a super arm. (ii) DFL-CSR [Tang et al., 2017] develops a UCB index for each base arm and selects a super arm at each time t based on a prior knowledge of a graph structure that shows the correlations among base arms. (iii) CTS [Huyuk and Tekin, 2019] employs Thompson sampling and uses an oracle to select a super arm at each time t. (iv) FTRL [Zimmert et al., 2019] selects a super arm at each time t based on the method of Follow-the-Regularized-Leader. To be comparable, we apply these benchmarks on the vector of overall reward yt at each time t. If a benchmark requires yt to be in [0, 1], we feed the normalized version of yt to the corresponding algorithm. Finally, in our experiments, we choose s = 6, meaning that the algorithms can choose 6 base arms at each time of play.

5.1 Synthetic Dataset

Our simulation setting is as follows. We first create a graph consisting of N = 20 nodes. The elements of the adjacency matrix A are drawn from a uniform distribution over [0.4, 0.7]. The edge density of the ground truth adjacency matrix is 0.15. At each time t, the vector of instantaneous rewards bt is drawn from a multivariate normal distribution with the support in [0, 1]20 and a spherical covariance matrix. As demonstrated in Section 2, we generate the vector of overall rewards according to the SEM in (3). We use g(A) = λ∥A∥1 as the regularization function in (10) when estimating the adjacency matrix A. The regularization parameter λ is tuned by grid search over [0.0001, 1000]. We evaluate the estimated adjacency matrix at each time t by using the mean squared error defined as MSE = 1 N 2 ∥∥∥A- ˆA∥∥∥2 F , where ∥·∥F denotes the Frobenius norm.

Comparison with the benchmarks. We run the algorithms using the aforementioned synthetic data with T = 4000. In Figure 2, we depict the trend of time-averaged expected regret for each policy. As we see, SEM-UCB surpasses all other policies. This is due to the fact that SEMUCB learns the network's topology and hence, it has a better knowledge of the causal relationships in the graph structure, unlike other policies that do not estimate the graph structure. As we see, the time-averaged expected regret of SEM-UCB tends to zero. This matches with our theoretical results in Section 4. Note that, the benchmark policies exhibit a suboptimal regret performance as they have to deal with nonidentically distributed random variables yt.

5.2 Covid-19 Dataset

We evaluate our proposed algorithm on the Covid-19 outbreak dataset of daily new infected cases during the pandemic in different regions within Italy. 1 The dataset fits in our framework as the daily new cases in each region results from the causal spread of Covid-19 among the regions in a country [Mastakouri and Sch¨olkopf, 2020] and the regionspecific characteristics [Guaitoli and Pancrazi, 2021]. As the regions differ in their regional characteristics, such as socioeconomic and geographical characteristics, each region has a specific exposure risk of Covid-19 infection. To be consistent with our terminology in Section 2, at each time (day) t, we use the overall reward yt[i] to refer to the overall daily new cases in region i and use the instantaneous reward bt[i] to refer to the region-specific daily new cases in region i. Naturally, the overall daily new cases includes the region-specific daily new cases of Covid-19 infection.

1 https://github.com/pcm-dpc/COVID-19

Governments around the world strive to track the spread of Covid-19 and find the regions that are contributing the most to the total number of daily new cases in the country [Bridgwater and B´ota, 2021]. By the end of this experiment, we address this critical problem and highlight that our algorithm is capable of finding the optimal candidate regions for political interventions in order to contain the spread of a contagious disease such as Covid-19.

Data preparation. We focus on the recorded daily new cases from 10 August to 15 October, 2020, for N = 21 regions within Italy. The Covid-19 dataset only provides us with the overall daily new cases of each region. Hence, in order to apply our algorithm, we need to infer the distribution of region-specific daily new cases for each region. In the following, we describe this process and further pre-processing of the Covid-19 dataset.

According to [Bull, 2021], for the time period from 18 May to 3 June, 2020, all places for work and leisure activities were opened and travelling within regions was permitted while travelling between regions was forbidden. Consequently, during this period, there are no causal effects on the overall daily new cases of each region from other regions. In addition, according to google mobility data [Nouvellet et al., 2021], during 4 weeks prior to 18 May the mobility was increasing within the regions while travel ban between the regions was still imposed. Hence, we use this expanded period to estimate the underlying distributions of the region-specific daily new cases using a kernel density estimation. Finally, considering that the daily recorded data noticeably fluctuates, a 7-day moving average was applied to the signals.

We create the region-specific daily new cases for each region by sampling from the estimated distributions. Below, we present the results of applying our algorithm on the preprocessed Covid-19 dataset. Since the data only contains the reported overall daily new cases for a limited time period, care should be exercised in interpreting the results. However, by providing more relevant data, our proposed framework helps towards more accurate detection of the regions that contribute the most to the development of Covid-19.

Learning the structural dependencies. Our algorithm learns the ground truth adjacency matrix A using (10). As for the choice of regularization function in (10), we employ Directed Total Variation (DTV) which is a novel application of the Graph Directed Variation (GDV) function [Sardellitti et al., 2017]. DTV regularization function is defined as

The regularization function addresses the smoothness of the entire observations Y over the underlying directed graph. To be more realistic, since the causal spread of the disease might create cycles, we additionally include cyclic graphs in the search space of the optimization problem (10).

We perform cross-validation technique to tune the regularization parameter λ. As mentioned before, we work on a limited time period with T = 66 days. Thus, we split the data into train and validation sets in 10:1 ratio. More specifically, we split the data into 6 subsets of 11 consecutive days. In each subset, one day is chosen uniformly at random to be included in the validation set while the remaining 10 days are added to the train set. We calculate the prediction error at each time t by

where K(t) is the validation set at time t with cardinality K(t) = |K(t)| and yi and ˆyi are the validation data and the corresponding predicted value using the estimated graph for day i, respectively. Figure 3 compares the ground truth overall daily new cases and the predicted overall daily new cases using the estimated graph on 4 different days of the Covid19 outbreak in our validation data. Due to space limitation, we use abbreviations for region names. Table 1 in Section 2.1 of supplementary material lists the abbreviations together with the original names of the regions. We observe that our proposed framework is capable to estimate the data for each region efficiently, that helps the agent to improve its decisionmaking process in a real-world scenario.

Learning regions with the highest contribution. In Figure 4, we show the decision-making process of the agent over time by following the SEM-UCB policy. Dark rectangles represent the 6 selected regions at each day (time). Based on our framework, we represent the selected regions by our algorithm as those with biggest contributions to the development of Covid-19 during the time interval considered in our experiment. More specifically, we find the regions of Lombardia, Emilia-Romagna, Lazio, Veneto, Piemonte, and Liguria as the ones that contribute the most to the spread of Covid-19 during that period in Italy.

We emphasize that, due to the causal effects among the regions, contribution of each region to the spread of covid-19 differs from its overall daily cases of infection. Thus, the set of regions with the highest contribution does not necessarily equal to the set of regions with the highest total number of daily cases. This is a key aspect of our problem formulation that is addressed by SEM-UCB in Figure 4. We elaborate more on this fact in Section 2.3 of supplementary material.

6 Conclusion

In this paper, we developed a combinatorial semi-bandit framework with causally related rewards, where we modelled the causal relations by a directed graph in a structural equation model. We developed a decision-making policy, namely SEM-UCB, that learns the structural dependencies to improve the decision-making process. We proved that SEMUCB achieves a sublinear regret bound in time. Our framework is applicable in a number of contexts such as network data analysis of biological networks or financial markets. We applied our method to analyze the development of Covid-19. The experiments showed that SEM-UCB outperforms several state-of-the-art combinatorial semi-bandit algorithms. Future research directions would be to extend the current framework to deal with piece-wise stationary environments where the causal graph and/or the expected instantaneous rewards of the base arms undergo abrupt changes over time.

Acknowledgements

This work was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy - EXC number 2064/1 - Project number 390727645, and by Grant 01IS20051 from the German Federal Ministry of Education and Research (BMBF). We are grateful to Sergio Barbarossa and Sofien Dhouib for fruitful discussions and comments.