Mutli-Armed Bandits with Network Interference

Weaknesses:

It took me a long time to realize that the effects were being estimated on a per-subset basis – ie, that chi^{a_i}(B(n)) is an indicator vector for the subset a_i intersected with the neighborhood of n. Originally I thought that chi^{a_i}(B(n)) =1 for all subsets of a_i, so I was very confused why we didn't have to worry about dependence among the entries of chi. If the authors can think of any way to clarify the exposition, I would greatly appreciate it. This is probably obvious to someone who is more familiar with Boolean Fourier analysis, but your readers may not be.

Thank you for helping us improve the exposition of our paper! We provide a simple example of (a) binary action embeddings and (b) the corresponding Fourier embeddings below. We will also revise the paper to reflect this example.

$**Binary action embedding**$. Consider $N$ units with 2 arms ($\mathcal{A} =2$), and a network graph $\mathcal{G}$ such that each unit $n$ is connected to one other unit, i.e., $\mathcal{G}$ has maximum degree 2. An action $\mathbf{a} = (a_{1}, \ldots a_{N}) \in \\{0,1\\}^N$, will induce the binary embedding $\mathbf{v}(\mathbf{a}) = (v(a_1), \ldots v(a_N)) \in \\{-1,1\\}^N$ where $v(a_i) = 1$ if $a_i$ is 1 and -1 if $a_i = 0$. For example, if $\mathbf{a} = (0,1,1 \ldots 1)$, then $\mathbf{v}(\mathbf{a}) = (-1,1,\ldots,1)$.

$**Fourier embedding**$. For any subset of units $S \subset [N]$, the Fourier character $\chi_{S}(\mathbf{v}(\mathbf{a})) = \prod_{i \in S} v(a_i)$. For instance, if the action $\mathbf{a} = (0,1,1 \ldots 1)$ as above, and the subset $S = \\{1,2\\}$, the Fourier character $\chi_{\\{1,2\\}}(\mathbf{v}(\mathbf{a})) = v(a_1) \times v(a_2) = -1$. The vector of Fourier characteristics $\boldsymbol{\chi}(\mathbf{a}) = (\chi_{S}(\mathbf{v}(\mathbf{a})) : S \subset N) \in \\{-1,1\\}^{2^N}$ is the concatenation of all Fourier characters for all subsets.

$**Fourier coefficient**$. Since each unit $n$ is only connected to one other unit $m$, unit n's neighborhood $\mathcal{N}(n) = \\{n,m\\}$ for a unit $m \neq n$. For unit $n$, the blocks $\mathcal{B}(n)$ are the indices of $\mathbf{v}(\mathbf{a})$ corresponding to treatments of units in $\mathcal{N}(n)$. For our network graph $\mathcal{G}$, $\mathcal{B}(n) = \\{v(a_n), v(a_m)\\}$. The subsets $S \in \mathcal{B}(n) = \\{\phi, \\{n\\}, \\{m\\}, \\{n,m\\} \\}$ correspond to the non-zero coefficients of unit n's Fourier coefficient $\boldsymbol{\theta}_{n} \in \mathbb{R}^{2^{N}}$.

This paper is very well-written. One thing that was missing from the exposition was an explanation of what the Fourier analysis buys us in this setting. What did the Fourier approach allow you to do in this problem that was not available using previous methods (for example, methods people have applied to combinatorial bandits)? From reading your appendices, I think the answer might be that the orthogonality of the basis functions makes it easy to bound the precision of theta. If you could clarify this it would help your method be adopted by a wider audience.

The Fourier basis provides a natural sparse linear representation of the network interference which is not easily done in other bases. To see this, we continue the example from the point above. Since $\boldsymbol{\theta}_{n}$ is 4-sparse, the reward $r_n (\mathbf{a}) = \langle \boldsymbol{\theta}_n, \boldsymbol{\chi} (\mathbf{a}) \rangle$ for unit $n$ can be represented using 4 Fourier characters: $\\{\chi\_{\phi}, \chi\_{n}, \chi\_{m}, \chi\_{\\{n,m\\}} \\}$. This representation captures sparsity unlike a 'one-hot' representation where the reward for unit $n$ can be represented as $r_n (\mathbf{a}) = \sum\_{\mathbf{a}' \in \\{0,1\\}^N}r_n(\mathbf{a}') \mathbf{1}[\mathbf{a} = \mathbf{a}']$. This one-hot basis also linearly expresses the reward but requires $2^N$ indicator basis vectors to do so. It is precisely this sparse linear representation induced by the Fourier basis that allows our bounds to scale with $2^s$ rather than $2^N$.

Questions:

This paper makes a novel contribution of translating the "MAB-with-interference" problem to a linear bandits problem using Fourier analysis. I don't understand why you can't then use existing solutions from the linear bandits literature to solve your problem, and take regret rates from there, instead of rederiving the rates for your own algorithm. Could you please clarify why you cannot apply the linear bandits results mentioned in the introduction to your problem?

We note that once we have mapped the network bandit problem into the corresponding Fourier basis, we still do not directly have a standard linear bandit problem. In particular, we are consider $N$ separate, simultaneous linear bandit problems (one for each unit), each with $\mathcal{A}^s$ possible actions. An additional aspect of our analysis is the aggregation of information over the various units to produce an estimate for the global average reward function.

Weaknesses:

Although the formulation is interesting, the algorithm design and analyses seem quite standard. After transforming to the functional space, it becomes the MAB problem with effectively $A^s$ arms. The ETC algorithm and the analysis of the estimation error as well as the regret have been studied in the literature. I wonder if the formulation alone is sufficient as the contribution of the paper.

We believe there are several main contributions to our paper outside of the formulation, which we enumerate below.

• First, as mentioned in the reviewer’s comment, the Fourier embedding of the unit-specific rewards is non-obvious and hasn’t been considered before in related literature.
• Second, once we have performed the transformation using the discrete Fourier transform, the problem is not just a MAB instance with $A^s$ arms, but rather $N$ simultaneous multi-armed bandit instances, each having $A^s$ arms. Thus, an additional step we must take in our argument (and a step that isn’t considered in more classical approaches to ETC) is that we must aggregate our confidence sets for unit-specific reward functions into a corresponding confidence set for the global reward.
• Third, we also provide a sequential elimination style algorithm which can obtain improved dependence on the time horizon $T$ in the regret bound. In particular, this style of algorithm gets the same dependence on $T$ as a UCB algorithm would.

Questions:

The paper takes an agnostic approach to the network structure. This is the strength of the algorithm. However, I wonder if there is room for the network structure. For example, it doesn't seem possible for the algorithm to incorporate some network information such as clusters and stars. Is it possible to adapt the algorithm to certain graphs?

In our paper, we consider a minimal assumption setting in which all we know is a bound on the size of the neighborhood of each unit. We opt not to make additional structural assumptions on the network (e.g. clusters, stars, etc.) for the sake of simplicity and generality. We believe that better regret rates may be able to be achieved by making structural assumptions (for instance, in this case we may be able to regress against low-degree polynomials in the Fourier space), but this is outside of the scope of the paper.

ETC is known to be not rate-optimal. I wonder why the authors don't use LinUCB algorithms in linear bandit at the first place. The problem can be viewed as linear bandit with a very large space, correct?

In the setting of unknown network structure (Section 5 of our paper), the given dependence on the time horizon $T$ is optimal (i.e. no algorithm can generally achieve dependence better than $O(T^{2/3})$). See [1] for details, as the authors construct a lower bound. In the setting of known network interference (Section 4 of our paper), we actually provide a sequential-elimination algorithm (Algorithm 3 in Appendix D) that obtains optimal regret dependence on the time horizon T (a rate of $O(T^{1/2})$). While we could additionally consider a UCB-style algorithm, this would likely be more difficult to analyze, and wouldn’t improve the regret rate, at least with respect to the time horizon $T$ (sequential elimination and LinUCB achieve the same rate). We re-emphasize that, even after mapping to the frequency space, we still are not in a vanilla linear bandit problem — we are actually in a setting where there are $N$ simultaneous, related bandit instances.

In Step 10 of Algorithm 1, how can the optimization problem be solved in practice given the large space?

Computing the optimal action is equivalent to just finding the maximum in a large list (a trivial optimization problem for modern computers). We note that at this point in the algorithm there are no constraints on the selected action.

[1] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753–10763, 2020.

Weaknesses:

On the one hand, Algorithm 1 performs well only when $N$ is very large (otherwise its better to use Algorithm 3), but it also has a running time of $\Omega(N)$, so it seems bad either way. Not sure why the focus is not on Algorithm 3 instead.

We chose to focus Section 4 on Algorithm 1 due to its simplicity and its similarity to the algorithm in the unknown interference structure case. We agree that Algorithm 3 likely offers a bound on regret in most parameter settings. For the final draft, we have added additional exposition about Algorithm 3 in Section 4 to better contrast the two approaches to regret minimization. In particular, we have added a theorem statement following the theorem statement for the “explore then commit” style algorithm.

Questions:

Various typos and formatting issues

Thank you for pointing out the various typos and the issue with our paper's formatting. We have corrected these issues for the final draft of the paper.

In your algorithms, can you clarify the running time of finding the minimizing coefficient vector?

The runtime of finding the minimizing coefficient vector (i.e., $\hat{\mathbf{\theta}}_n$) is equivalent to solving an ordinary least squares or Lasso for $N$ units when the graph structure is known and unknown respectively. There exists efficient gradient-based algorithms for solving these linear programs. We note that our algorithms are designed such that each of these linear programs can be solved in parallel for each unit independently which significantly reduces runtime.

Weaknesses:

The paper lacks real examples to demonstrate the combination of online experimentation and interference. Perhaps the combination is as natural as the paper suggests. For example, In online experimentation, after every action, it may take some time for the interference to occur. If we measure the outcome right after the action, it may provide no information about the effect of interference on the reward.

A concrete example is given by online bidding in advertisement; the “agent” here is a centralized platform that coordinates at each round bids coming from N advertisers. Advertisers submit bids and compete in an auction: winning advertisers get to display the ad. Treatments here correspond to different pricing schemes imposed by the platform. For example, two different treatments might correspond to different reserve prices imposed on advertisers (e.g., a higher or lower premium paid at ad-display time). The reward function measures the downstream conversions driven by ads. Here, it is natural to assume that the reward for one advertiser will only be impacted by the behavior (impacted by the treatment) of a subset of the total population of advertisers, e.g., direct competitors.

The paper should discuss Assumption 2 more. For example, the upper bound s needs to hold for all units n. Suppose s is very large or small. It is unclear how this affects the algorithms presented later.

Our algorithms leverage knowledge of the sparsity (or at least an upper bound on the sparsity s) in determining the length of the exploration period. As noted in Remark 4.6 in [1], we can select the length of the exploration period to be independent of the sparsity, but we will pay an additional cost in regret of $O(A^{s/3})$. We have added a comment noting this in the appropriate sections. If one is concerned about practical applications of our algorithms, cross-validation can be used to select the length of the exploration period, as outlined in our remark at the end of Section 4. We also note that such sparsity assumptions are common in both network causal inference literature and the high-dimensional statistics literature.

It is unclear if we can apply the offline methods under interference to online settings. Maybe we could use these methods to estimate the reward function at every step and then take action by maximizing the reward function.

We note that the goals of problems considered in the offline setting are not the same as those considered in the online setting. In the offline setting, the goal of the learner is typically to (a) estimate some sort of treatment effect in the presence of network interference and (b) produce a confidence interval/set for the parameter estimate. The experiments designed to accomplish these tasks often involve uniform/random exploration over the entire time period, and thus would yield linear regret. In the online setting, we want to minimize regret. While we do estimate the underlying global reward functions, this is just a nuisance parameter in our setting. What we really care about is (a) quickly discovering a (nearly) action and (b) exploiting this action over many time steps. This difference is what necessitates different algorithms.

[1] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753–10763, 2020.

Weaknesses:

The Boolean encoding of the actions is not well-discussed.

Thank you for helping us improve the exposition of our paper! We provide a simple example of (a) binary action embeddings and (b) the corresponding Fourier embeddings below. Further, we describe how the Fourier representation naturally captures our sparse network interference assumption unlike other potential representations. This example can be found in the response to all reviewers above, but we discuss it here for convenience. We will also revise the paper to reflect this example.

$**Binary action embedding**$. Consider $N$ units with 2 arms ($\mathcal{A} =2$), and a network graph $\mathcal{G}$ such that each unit $n$ is connected to one other unit, i.e., $\mathcal{G}$ has maximum degree 2. An action $\mathbf{a} = (a_{1}, \ldots a_{N}) \in \\{0,1\\}^N$, will induce the binary embedding $\mathbf{v}(\mathbf{a}) = (v(a_1), \ldots v(a_N)) \in \\{-1,1\\}^N$ where $v(a_i) = 1$ if $a_i$ is 1 and -1 if $a_i = 0$. For example, if $\mathbf{a} = (0,1,1 \ldots 1)$, then $\mathbf{v}(\mathbf{a}) = (-1,1,\ldots,1)$.

$**Fourier embedding**$. For any subset of units $S \subset [N]$, the Fourier character $\chi_{S}(\mathbf{v}(\mathbf{a})) = \prod_{i \in S} v(a_i)$. For instance, if the action $\mathbf{a} = (0,1,1 \ldots 1)$ as above, and the subset $S = \\{1,2\\}$, the Fourier character $\chi_{\\{1,2\\}}(\mathbf{v}(\mathbf{a})) = v(a_1) \times v(a_2) = -1$. The vector of Fourier characteristics $\boldsymbol{\chi}(\mathbf{a}) = (\chi_{S}(\mathbf{v}(\mathbf{a})) : S \subset N) \in \\{-1,1\\}^{2^N}$ is the concatenation of all Fourier characters for all subsets.

$**Fourier coefficient**$. Since each unit $n$ is only connected to one other unit $m$, unit n's neighborhood $\mathcal{N}(n) = \\{n,m\\}$ for a unit $m \neq n$. For unit $n$, the blocks $\mathcal{B}(n)$ are the indices of $\mathbf{v}(\mathbf{a})$ corresponding to treatments of units in $\mathcal{N}(n)$. For our network graph $\mathcal{G}$, $\mathcal{B}(n) = \\{v(a_n), v(a_m)\\}$. The subsets $S \in \mathcal{B}(n) = \\{\phi, \\{n\\}, \\{m\\}, \\{n,m\\} \\}$ correspond to the non-zero coefficients of unit n's Fourier coefficient $\boldsymbol{\theta}_{n} \in \mathbb{R}^{2^{N}}$.

$**Fourier basis captures sparsity**$. Since $\boldsymbol{\theta}_{n}$ is 4-sparse, the reward $r_n (\mathbf{a}) = \langle \boldsymbol{\theta}_n, \boldsymbol{\chi} (\mathbf{a}) \rangle$ for unit $n$ can be represented using 4 Fourier characters: $\\{\chi\_{\phi}, \chi\_{n}, \chi\_{m}, \chi\_{\\{n,m\\}} \\}$. This representation captures sparsity unlike a 'one-hot' representation where the reward for unit $n$ can be represented as $r_n (\mathbf{a}) = \sum\_{\mathbf{a}' \in \\{0,1\\}^N}r_n(\mathbf{a}') \mathbf{1}[\mathbf{a} = \mathbf{a}']$. This one-hot basis also linearly expresses the reward but requires $2^N$ indicator basis vectors to do so. It is precisely this sparse linear representation induced by the Fourier basis that allows our bounds to scale with $2^s$ rather than $2^N$.

In Fig 2(b), it seems that the regret stops accumulating when T is larger enough. Is it true? Could you give a discuss why it happens?

The regression algorithm (either OLS in the case of Algorithm 1 or the Lasso in the case of Algorithm 2) estimates the unknown global reward function with a high-degree of accuracy at the end of the exploration phase. In more detail, we have that (with high probability) $|\widehat{r}(a) - \bar{r}(a)| < \epsilon$ for all actions $a$, where $\epsilon$ is some small value denoting the width of the confidence interval. In the case that the suboptimality gap (i.e. the gap in reward between the best and second best action) is smaller than $\epsilon$, we are guaranteed to select the optimal action. That is, we incur zero regret during the exploitation phase.

Questions:

The authors studied the interference over the underlying network of units, I wonder if it's possible to consider the impact over time, i.e., the reward may rely on previous actions that its neighbors received, for example, the impact decays exponentially over time.

We believe investigating the effects of an entire history of treatments on the current period is both interesting and practically-relevant. Given that the current approach for estimating rewards depends heavily on the unknown, unit-specific reward functions being fixed over the rounds of interaction, additional machinery would almost surely need to be developed to handle this generalization. Here is perhaps one possible approach:

• If the dependence of present reward (say in round $t$) on historical treatments decays geometrically, it may be possible to “extend” the action space to tuples of actions played over the past $s$ rounds (i.e. tuple of the form $(a_t, a_{t - 1}, \dots, a_{t - s})$. We can then suffer some “truncation” error for ignoring the given treatments in rounds $t -s -1, t-s -2$, etc. This truncation error can be computed based on the geometric rate of decay, and $s$ can likely be chosen with respect to the time horizon $T$ to obtain small regret. Additionally, machinery from the reinforcement learning literature may be applicable to handling time-dependent rewards. We note that both aforementioned approaches fall outside of the scope of this paper, and thus we leave them for future work.

Weaknesses:

One potential weakness of the paper is that it provides limited proof sketches on results related leveraging the sparse network.

We agree that a proof sketch would help the reader better understand our algorithm and its convergence. If accepted, we will use the additional page to add brief proof sketches following the theorem statements.

The paper also only briefly touches upon settings where the graph is partially observed. The prescribed solution in these settings is to use the fully observed algorithm if "all" the neighbors of the unit are observed and to use the unobserved algorithm if the neighbors are not observed. It still seems unclear what should happen if only "some" of the neighbors are observed. Perhaps additional detail can be added to clarify.

If only some of the neighbors are observed, or if the practitioner has any doubt about whether a given edge is present in the graph/network, it is likely best practice to use the Algorithm 2 (i.e. the algorithm for the fully-unobserved graph case). We note that both in theory and in our simulations, the performance of this algorithm is not much worse than that of Algorithm 1. Moreover, we emphasize that neither the fully or partially observed settings have been studied before this paper. While it may be possible to derive algorithms for particular forms of unobserved structure, it falls outside of the scope of our work. We have added clarification about this point in the paper.

Questions:

Does the sparse network model effectively capture interference effects that decay depending on how related two units are?

Our paper considers a worst-case setting in which the reward/outcomes associated with each unit can depend arbitrarily on the treatments assigned to its neighbors. We believe that better regret rates are possible if additional structure is assumed, e.g. that the reward satisfies a “bounded difference” property and is not very sensitive to a change in treatment for any given individual unit. Deriving algorithms that can leverage additional structural assumptions is likely a non-trivial task, so we leave it for future work.

If only a portion of neighbors is revealed for unit i, do you use Algorithm 1 or Algorithm 2?

In this case, the learner should use Algorithm 2.