Near-Optimal Algorithms for Piecewise-Stationary Cascading Bandits
Near-Optimal Algorithms for Piecewise-Stationary Cascading Bandits
复制标题
DOI：
10.1109/icassp39728.2021.9414506
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Lingda Wang;Huozhi Zhou;Bingcong Li;L. Varshney;Zhizhen Zhao
中科院分区：
文献类型：
--
作者：
Lingda Wang;Huozhi Zhou;Bingcong Li;L. Varshney;Zhizhen Zhao
级联强盗（CB）是一种流行的网络搜索和在线广告模型。然而，静态CB模型可能过于简单，无法科普现实世界的问题，其中用户偏好可能会随着时间的推移而变化。考虑到分段平稳环境，提出了两种有效的算法：GLRT-CascadeUCB和GLRT-CascadeKL-UCB。与现有算法相比，所提算法具有以下优点：（1）不需要变点相关的参数选择信息;（2）调整参数少;（3）改进了后悔上界。我们还表明，所提出的算法是最佳的对数项推导出一个极大极小下界$\欧米茄（\sqrt {NLT}）$分段平稳CB。通过对真实世界基准数据集的数值测试，验证了所提出的算法的效率。
Cascading bandit (CB) is a popular model for web search and online advertising. However, the stationary CB model may be too simple to cope with real-world problems, where user preferences may change over time. Considering piecewise-stationary environments, two efficient algorithms, GLRT-CascadeUCB and GLRT-CascadeKL-UCB, are developed. Comparing with existing works, the proposed algorithms: i) are free of change-point-dependent information for choosing parameters; ii) have fewer tuning parameters; iii) improve regret upper bounds. We also show that the proposed algorithms are optimal up to logarithm terms by deriving a minimax lower bound $\Omega (\sqrt {NLT} )$ for piecewise-stationary CB. The efficiency of the proposed algorithms is validated through numerical tests on a real-world benchmark dataset.