Online experimentation with interference is a common challenge in modern
applications such as e-commerce and adaptive clinical trials in medicine. For
example, in online marketplaces, the revenue of a good depends on discounts
applied to competing goods. Statistical inference with interference is widely
studied in the offline setting, but far less is known about how to adaptively
assign treatments to minimize regret. We address this gap by studying a
multi-armed bandit (MAB) problem where a learner (e-commerce platform)
sequentially assigns one of possible $\mathcal{A}$ actions (discounts) to $N$
units (goods) over $T$ rounds to minimize regret (maximize revenue). Unlike
traditional MAB problems, the reward of each unit depends on the treatments
assigned to other units, i.e., there is interference across the underlying
network of units. With $\mathcal{A}$ actions and $N$ units, minimizing regret
is combinatorially difficult since the action space grows as $\mathcal{A}^N$.
To overcome this issue, we study a sparse network interference model, where the
reward of a unit is only affected by the treatments assigned to $s$ neighboring
units. We use tools from discrete Fourier analysis to develop a sparse linear
representation of the unit-specific reward $r_n: [\mathcal{A}]^N \rightarrow
\mathbb{R} $, and propose simple, linear regression-based algorithms to
minimize regret. Importantly, our algorithms achieve provably low regret both
when the learner observes the interference neighborhood for all units and when
it is unknown. This significantly generalizes other works on this topic which
impose strict conditions on the strength of interference on a known network,
and also compare regret to a markedly weaker optimal action. Empirically, we
corroborate our theoretical findings via numerical simulations.

通过研究在线干预实验中的干扰问题，我们提出了基于线性回归算法的多臂赌博机策略，以最小化后悔并实现低后悔的任务分配。