(Private) Kernelized Bandits with Distributed Biased Feedback
(Private) Kernelized Bandits with Distributed Biased Feedback
复制标题
具有分布式偏差反馈的（私人）内核化强盗
DOI：
10.1145/3579318
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Ji, Bo
中科院分区：
文献类型：
--
作者：
Li, Fengjiao;Zhou, Xingyu;Ji, Bo
在本文中，我们研究具有分布式偏置反馈的核化老虎机。这个问题是由几个现实世界的应用程序（例如动态定价、蜂窝网络配置和政策制定）引起的，其中大量用户为中央实体选择的操作提供奖励，但很难收集所有用户的反馈。相反，只有来自用户子集的有偏见的反馈（由于用户异质性）可能是可用的。除了这种部分有偏差的反馈之外，由于通信成本和计算复杂性，我们还面临着两个实际挑战。为了应对这些挑战，我们精心设计了一种新的分布式基于阶段和批次的消除（DPBE）算法，该算法分阶段对用户进行采样以收集反馈以减少偏差，并采用最大方差减少来在每个阶段内批量选择操作。通过正确选择阶段长度、批量大小和用于消除次优动作的置信宽度，我们表明 DPBE 实现了 ~O(T1-α/2 +√γT T) 的次线性遗憾，其中 α ∈ (0,1) 是可以调整的用户采样参数。此外，与最先进算法的某些变体（最初为标准内核化 bandits 开发）相比，DPBE 可以显着降低分布式内核化 bandits 中的通信成本和计算复杂性。此外，通过结合各种差分隐私模型（包括中央模型、局部模型和洗牌模型），我们推广了DPBE，为参与分布式学习过程的用户提供隐私保证。最后，我们进行了广泛的模拟来验证我们的理论结果并评估实证性能。
In this paper, we study kernelized bandits with distributed biased feedback. This problem is motivated by several real-world applications (such as dynamic pricing, cellular network configuration, and policy making), where users from a large population contribute to the reward of the action chosen by a central entity, but it is difficult to collect feedback from all users. Instead, only biased feedback (due to user heterogeneity) from a subset of users may be available. In addition to such partial biased feedback, we are also faced with two practical challenges due to communication cost and computation complexity. To tackle these challenges, we carefully design a new distributed phase-then-batch-based elimination (DPBE) algorithm, which samples users in phases for collecting feedback to reduce the bias and employs maximum variance reduction to select actions in batches within each phase. By properly choosing the phase length, the batch size, and the confidence width used for eliminating suboptimal actions, we show that DPBE achieves a sublinear regret of ~O(T1-α/2 +√γT T), where α ∈ (0,1) is the user-sampling parameter one can tune. Moreover, DPBE can significantly reduce both communication cost and computation complexity in distributed kernelized bandits, compared to some variants of the state-of-the-art algorithms (originally developed for standard kernelized bandits). Furthermore, by incorporating various differential privacy models (including the central, local, and shuffle models), we generalize DPBE to provide privacy guarantees for users participating in the distributed learning process. Finally, we conduct extensive simulations to validate our theoretical results and evaluate the empirical performance.
登录
查看更多内容
Auric：使用数据驱动的推荐自动生成蜂窝配置
DOI：
10.1145/3452296.3472906
发表时间：
2021
期刊：
Proceedings of the 2021 ACM SIGCOMM 2021 Conference
影响因子：
--
作者：
A. Mahimkar;A. Sivakumar;Zihui Ge;Shomik Pathak;Karunasish Biswas
通讯作者：
Karunasish Biswas
内核和神经强盗的纯粹探索
DOI：
--
发表时间：
2021
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Zhu, Yinglun;Zhou, Dongruo;Jiang, Ruoxi;Gu, Quanquan;Willett, Rebecca;Nowak, Robert
通讯作者：
Nowak, Robert
DOI：
--
发表时间：
2021-10
期刊：
ArXiv
影响因子：
--
作者：
Zihan Li;J. Scarlett
通讯作者：
Zihan Li;J. Scarlett
DOI：
10.23919/wiopt56218.2022.9930524
发表时间：
2022-07
期刊：
2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)
影响因子：
--
作者：
Fengjiao Li;Xingyu Zhou;Bo Ji
通讯作者：
Fengjiao Li;Xingyu Zhou;Bo Ji
DOI：
10.48550/arxiv.2203.15589
发表时间：
2022-03
期刊：
ArXiv
影响因子：
--
作者：
Xingyu Zhou;Bo Ji
通讯作者：
Xingyu Zhou;Bo Ji