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

作者：卢世银; 王广辉; 邱梓豪; 张利军^*

来源：软件学报, 2022, 33(09): 3223-3235.

DOI：10.13328/j.cnki.jos.006386

• 图赌博机
• 差分隐私
• 不确定性环境下的序列决策
• 独立集
• 拉普拉斯噪声

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

• 单位
  南京大学; 计算机软件新技术国家重点实验室