一种满足差分隐私的图赌博机算法

Differentially Private Algorithm for Graphical Bandits

图赌博机是一种重要的不确定性环境下的序列决策模型,在社交网络、电子商务和推荐系统等领域都得到了广泛的应用.目前,针对图赌博机的工作都只关注如何快速识别最优摇臂从而最小化累积遗憾,而忽略了在很多应用场景中存在的隐私保护问题.为了克服现有图赌博机算法的缺陷,提出了一种满足差分隐私的图赌博机算法GAP(图反馈下的差分隐私摇臂消除策略).一方面,GAP算法阶段性地根据摇臂的经验平均奖赏更新摇臂选取策略,并在计算摇臂的经验平均奖赏时引入拉普拉斯噪声,从而确保恶意攻击者难以根据算法输出推算摇臂奖赏数据,保护了隐私.另一方面,GAP算法在每个阶段根据精心构造的反馈图的独立集探索摇臂集合,有效地利用了图形式的反馈信息.证明了GAP算法满足差分隐私性质,具有与理论下界相匹配的遗憾界.在仿真数据集上的实验结果表明:GAP算法在有效保护隐私的同时取得了与现有无隐私保护的图赌博机算法相当的累积遗憾.

Graphical bandit is an important model for sequential decision making under uncertainty and has been applied in various realworld scenarios such as social network, electronic commerce, and recommendation system. Existing work on graphical bandits only investigates how to identify the best arm rapidly so as to minimize the cumulative regret while ignoring the privacy protection issue arising in many real-world applications. To overcome this deficiency, a differentially private algorithm is proposed, termed as graph-based arm elimination with differential privacy(GAP), for graphical bandits. On the one hand, GAP updates the arm selection strategy based on empirical mean rewards of arms in an epoch manner. The empirical mean rewards are perturbed by Laplace noise, which makes it hard for malicious attackers to infer rewards of arms from the output of the algorithm, and thus protects the privacy. On the other hand, in each epoch, GAP carefully constructs an independent set of the feedback graph and only explores arms in the independent set, which effectively utilize the information in the graph feedback. It is proved that GAP is differential private and its regret bound matches the theoretical lower bound. Experimental results on synthetic datasets demonstrate that GAP can effectively protect the privacy and achieve cumulative regret comparable to that of existing non-private graphical bandits algorithm.