Variance-Adaptive Algorithm for Probabilistic Maximum Coverage Bandits with General Feedback
Variance-Adaptive Algorithm for Probabilistic Maximum Coverage Bandits with General Feedback
复制标题
DOI：
10.1109/infocom53939.2023.10228940
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Xutong Liu;Jinhang Zuo;Hong Xie;Carlee Joe-Wong;John C.S. Lui
中科院分区：
文献类型：
--
作者：
Xutong Liu;Jinhang Zuo;Hong Xie;Carlee Joe-Wong;John C.S. Lui
概率最大覆盖（PMC）是一个重要的问题，它可以对许多网络应用进行建模，包括移动众测、网络内容交付和动态信道分配，其中运营商在图中选择可以概率覆盖其他节点的节点。本文研究在线学习背景下的PMC: PMC匪帮。对于网络参数先验未知的PMC强盗，决策者需要学习未知参数，目标是使覆盖节点的总回报最大化。虽然之前已经对PMC强盗进行了研究，但是现有的模型和相应的算法可以得到很大的改进。首先，我们提出了PMC- g强盗，其反馈模型概括了现有的半强盗反馈，允许PMC强盗建模在线内容分发和在线动态渠道分配等应用。其次，我们通过引入方差自适应算法，即VA-CUCB算法，改进了现有的组合上置信度界（CUCB）算法。我们证明了VA-CUCB可以获得严格更好的后悔边界，它将CUCB改进了一个因子$\tilde O(K)$，其中K为每轮选择的节点数。最后，在合成数据集和真实数据集上进行了实验，并与基准算法进行了比较。
Probabilistic maximum coverage (PMC) is an important problem that can model many network applications, including mobile crowdsensing, network content delivery, and dynamic channel allocation, where an operator chooses nodes in a graph that can probabilistically cover other nodes. In this paper, we study PMC under the online learning context: the PMC bandit. For PMC bandit where network parameters are not known a priori, the decision maker needs to learn the unknown parameters and the goal is to maximize the total rewards from the covered nodes. Though PMC bandit has been studied previously, the existing model and its corresponding algorithm can be significantly improved. First, we propose the PMC-G bandit whose feedback model generalizes existing semi-bandit feedback, allowing PMC bandit to model applications like online content delivery and online dynamic channel allocation. Next, we improve the existing combinatorial upper confidence bound (CUCB) algorithm by introducing the variance-adaptive algorithm, i.e., the VA-CUCB algorithm. We prove that VA-CUCB can achieve strictly better regret bounds, which improves CUCB by a factor of $\tilde O(K)$, where K is the number of nodes selected in each round. Finally, experiments show our superior performance compared with benchmark algorithms on synthetic and real-world datasets.