针对网络干扰下的多臂老虎机，提出基于图结构的近优算法。
Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference
- 利用局部图结构设计算法，降低计算复杂度
- 理论证明在稠密与稀疏图上均接近最优
- 适用于干扰图未知场景，具帕累托最优性
我们研究网络干扰下的多臂老虎机问题，其中每个单元的收益依赖于自身及邻接节点的处理结果。这导致动作空间呈指数级增长，使标准方法计算不可行。本文提出一种新算法，利用局部图结构最小化累计遗憾。推导出依赖图结构的上界，优于已有工作。此外，首次给出任意网络干扰下带模型的下界，每个下界对应图的不同结构性质。结果表明，对稠密与稀疏图，该算法近乎最优，上下界仅差对数因子。当干扰图未知时，其变体具有帕累托最优性：不存在算法能在所有实例中统一优于它。数值实验验证了该方法优于基线方法。
原文摘要 · Abstract (English)
We study multi-armed bandits under network interference, where each unit's reward depends on its own treatment and those of its neighbors in a given graph. This induces an exponentially large action space, making standard approaches computationally impractical. We propose a novel algorithm that uses the local graph structure to minimize regret. We derive a graph-dependent upper bound on cumulative regret that improves over prior work. Additionally, we provide the first lower bounds for bandits with arbitrary network interference, where each bound involves a distinct structural property of the graph. These bounds show that for both dense and sparse graphs, our algorithm is nearly optimal, with matching upper and lower bounds up to logarithmic factors. When the interference graph is unknown, a variant of our algorithm is Pareto optimal: no algorithm can uniformly outperform it across all instances. We complement our theoretical results with numerical experiments, showing that our approach outperforms the baseline methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。