Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits

Thank you for your insightful comments. We appreciate the feedback and would like to share our responses below.

1. Definition of Regret:

Alternatively, one could define the benchmark to be the optimal "personalized" treatment assignment from a function class $\mathcal{F}$. In this case, our analysis still applies—for instance, the expected regret bound scales with a factor of $\sqrt{|\mathcal{F}|}.$ We note that this "personalized" benchmark was used in Agarwal et al 2024, however, the cost paid for choosing this stronger benchmark is that the environment was assumed to be stationary.

It’s also worth noting that the same critique could be made of many foundational works in causal inference, which focus on the ATE effect between all-1 and all-0 policies. While these benchmarks appear simplistic, they are far from trivial and have led to a rich body of work in causal inference. Of course, policy learning - finding a good mapping from covariates to treatment — is a natural extension. But it is viewed as a more advanced goal, and builds upon insights from the fixed-policy setting, analogous the one in this work.

2. Expected regret vs h.p. regret:

It is true that a h.p. bound can be obtained by treating the entire system as a single “unit” and applying h.p.bounds for EXP-IX (as we discussed at the end of the intro and the start of section 4). However, this approach completely ignores N, and as a result, the tail probability does not vanish with increasing N. This dependence on N is crucial, especially in practical applications where $N \gg T.$ In fact, we dedicate Section 4.5 specifically to discussing this distinction.

From a practical standpoint, a “pure” switchback policy—where the entire system flips between treatment and control—is rarely used. Instead, tech firms typically partition the space into clusters and independently assign treatment or control to each cluster in each period. This is precisely what our algorithm is designed to capture. A concrete example is DoorDash’s use of “clustered” switchback experiments: https://careersatdoordash.com/blog/experiment-rigor-for-switchback-experiment-analysis/ In this sense, a key contribution of our work is to lay the theoretical foundation for a policy class that are widely deployed in industry.

While we mentioned the phrase “vanishing in N” in the abstract and other parts of the paper, we agree that this could have been more clearly emphasized. If the paper is accepted, we will revise accordingly to better highlight this point.

3. Discussion of stochastic and adversarial bandits in the literature review.

This is a fair point. To clarify, our claim that the adversarial setting is more general than the stochastic one assumes that the reward distribution has bounded support. That said, for the purposes of algorithm design and analysis, assuming sub-Gaussian noise with bounded mean behaves similarly to the bounded reward setting (e.g., Bernoulli rewards).

4. Examples/references for the Decaying Interference Property

As we mentioned right before Defn 2.3, this Decaying Interference Property (DIP) is borrowed from Leung 2022. The best way to motivate the the DIP is by noting that it generalizes several natural interference models that are well-known in the literature, including:

• (a) SUTVA (see our remark 2.4 right after def 2.3);
• (b) k-neighborhood model, where two units interfere with each other if there distance is at most k;
• (c) Cliff-Ord autoregressive model, where the treatment effect on unit u is a linear combination of the treatment effects on its direct neighbors (plus base effects). In this case, we have $\psi(r) = r^{-2}.$

Thanks for your feedback.

"How does the choice of the learning rate and the IX parameter beta affect the performance of the proposed method?"

Good question. Intuitively, $\beta$ controls the forced exploration of arms with low score. This aligns very well with Theorem 4.6, where $\beta$ appears in both terms B and C. In fact, B corresponds to the tail mass, and a small $\beta$ (which means less exploration) would cause the tail mass to go up. On the other hand, C is the regret caused by the bias (due to both interference and bias in the estimator). If $\beta$ is away from the "sweet spot", the HT estimator has a high bias.

Thanks again for this question, which helps improve the clarity of our results. If accepted, we will add these discussions to the paper.

Thanks for the feedback.

Q: "It is not completely clear methodology-wise what is the essential difference between stochastic bandits that consider possibly more general notions of interference and the present paper that considers a specific notion of interference and adversarial reward."

A: Good question. There are two disadvantages of the stochastic (i.i.d. reward) bandits analog:

• Practicality: Real-world A/B testing involves highly dynamic and heterogeneous environments;
• Technicality: If the rewards are iid, the problem wouldn't be too different Leung 2022. In fact, all we need to do is to combine their low-error estimator with a known paradigm for stochastic bandits, such as UCB.

That said, we do agree that the inclusion of a dedicated section on the stochastic version would provide a more complete picture, and we will do so if accepted.

Q: "How does the computational complexity analysis of the proposed algorithm look like?"

A: The bottleneck in terms of the time complexity lies in computing the estimator. Fix an arm. For each unit $u$, we need to compute the exposure mapping probability. this involves examining the arm assigned to each of the $O((r/\ell)^2)$ clusters that are close to $u$. Therefore, the total run time per round is $O(kN (r/\ell)^2)$. (Note that $r/\ell\le \sqrt N$)

Thanks for your feedback!

Q: "In the classic reference 'Logarithmic regret algorithms for online convex optimization' by Hazan et al., it is shown how regret bounds can be converted into ..."

A: This is an interesting thought. First, their result is not applicable to this work, since our reward functions are defined on a discrete domain and thus we can not define convexity (at least in the ordinary sense). But your intuition is right - if the reward function has a special form, such as linear in the neighbors treatment assignments (e.g. Cliff-Ord model) then there exists an estimator with lower error, and this would lead to better regret guarantees. This can be an interesting direction for future work.

Q: On the topic of cluster-based randomized experimentation, the authors may also wish to cite "On the topic of cluster-based randomized experimentation, the authors may also wish to cite "Detecting Network Effects: Randomizing Over Randomized Experiments", by Saveski, et al."

A: Yes, this is a relevant work; we will cite it in the updated version.