Contextual Combinatorial Bandits with Probabilistically Triggered Arms
Contextual Combinatorial Bandits with Probabilistically Triggered Arms
复制标题
DOI：
10.48550/arxiv.2303.17110
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Xutong Liu;Jinhang Zuo;Siwei Wang;John C.S. Lui;M. Hajiesmaili;A. Wierman;Wei Chen
中科院分区：
文献类型：
--
作者：
Xutong Liu;Jinhang Zuo;Siwei Wang;John C.S. Lui;M. Hajiesmaili;A. Wierman;Wei Chen
我们研究了在各种平滑条件下具有概率触发臂（C$^2$MAB-T）的上下文组合老虎机，这些条件捕获了广泛的应用，例如上下文级联老虎机和上下文影响最大化老虎机。在触发概率调制（TPM）条件下，我们设计了C$^2$-UCB-T算法，并提出了一种新颖的分析方法，实现了$\tilde{O}(d\sqrt{KT})$后悔界限，消除了潜在的指数大因子$O(1/p_{\min})$，其中$d$是上下文的维度，$p_{\min}$是任何arm可以被触发的最小正概率，batch-size $K$是每轮可以触发的最大武器数量。在方差调制（VM）或触发概率和方差调制（TPVM）条件下，我们提出了一种新的方差自适应算法VAC$^2$-UCB，并推导出一个后悔界限$\tilde{O}(d\sqrt{T})$，它与批量大小$K$无关。作为一个有价值的副产品，我们的分析技术和方差自适应算法可以应用于 CMAB-T 和 C$^2$MAB 设置，从而改善现有结果。我们还进行了一些实验，证明我们的算法与合成和真实数据集上的基准算法相比性能有所提高。
We study contextual combinatorial bandits with probabilistically triggered arms (C$^2$MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C$^2$-UCB-T algorithm and propose a novel analysis that achieves an $\tilde{O}(d\sqrt{KT})$ regret bound, removing a potentially exponentially large factor $O(1/p_{\min})$, where $d$ is the dimension of contexts, $p_{\min}$ is the minimum positive probability that any arm can be triggered, and batch-size $K$ is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC$^2$-UCB and derive a regret bound $\tilde{O}(d\sqrt{T})$, which is independent of the batch-size $K$. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C$^2$MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets.