编者按
随着个人数据被广泛应用于机器学习、推荐系统和在线服务中，如何保护用户隐私成为了一个迫切的问题。差分隐私作为一种强有力的隐私保护技术，能够有效防止数据泄露和滥用。而线性情景多臂老虎机问题则是许多实际应用中的核心问题，如在线广告投放、个性化推荐等，它要求系统在不确定环境中做出最优决策以最大化收益。本文重点介绍如何将差分隐私和线性情景多臂老虎机问题结合，从而实现在保护用户隐私的前提下进行精准决策，为数字经济时代的个人隐私和数据安全提供有力保障。
1、多臂老虎机问题
多臂老虎机问题是强化学习中的一个经典问题。假设有 种可行的决策集合 ,在时刻 ,智能体从 中选择一个决策 并得到一个该决策对应的随机报酬 。智能体的目标是通过尝试不同的决策来最大化累计报酬，或最小化累计遗憾值（Regret） 。
（图片来源：https://gibberblot.github.io/rl-notes/single-agent/multi-armed-bandits.html）
多臂老虎机问题重点研究 关于的增长速率，一个好的策略应该满足 。例如 还是 ?
2、线性情景多臂老虎机问题
线性情景多臂老虎机问题是传统问题的一个推广。下面是情景多臂老虎机所针对的问题场景：(1)推荐系统：不同用户喜爱的内容有所不同，通过结合用户的特征如人工统计学信息、历史浏览记录等，算法能够实现个性化推荐，从而提高用户体验和满意度。(2)广告投放：根据用户画像等情景信息，优化广告投放策略，提高广告的点击率和转化率。
定义为时刻的情景信息，期望报酬依赖于特征向量 ，即。文献中通常假设报酬函数为线性函数，即存在一个未知向量满足。智能体需要通过和环境交互来估计参数。
（图片来源：https://help.aliyun.com/zh/airec/what-is-pai-rec/use-cases/contextual-bandit-algorithms）
本文假设在决策时刻，智能体被给定一个决策集，其包含了所有提前计算的特征向量。智能体选择一个，其对应了一个决策 。因此，本文考虑的线性情景多臂老虎机问题的序列决策过程为（1）智能体收到一个决策集;（2）选择一个决策;(3)获得随机报酬。智能体的决策目标为最小化累计遗憾值 。
3、差分隐私
差分隐私（Differential Privacy）是一种隐私保护模型，其目的是确保数据在进行分析、查询和发布时，不会泄露具体信息。差分隐私要求在一次统计查询的数据集中增加或减少一条记录，可以获得几乎相同的输出，即任何一条记录的存在与否对结果的影响可忽略不计，从而无法从结果中还原出任何一条原始的记录。
（图片来源：https://en.wikipedia.org/wiki/Differential_privacy）
定义1 -差分隐私：令 表示一个非负实数， 表示一个随机算法。算法满足 -差分隐私如果对于任意的数据集 和 ，其存在一条数据不同，对于任意的的输出子集:
本文假设，情景和报酬信息是用户的私有信息，需要确保数据隐私。本文引入了连续观测值下的联合差分隐私的概念。定义两个序列和为-近邻如果对于任意的有。
定义2 联合差分隐私：一个针对线性情景多臂老虎机问题的随机算法在连续观测值下满足联合差分隐私，如果对于任意的和任何一组-近邻序列和,和任何子集序列，有
4、带有变动正则项的线性UCB算法
线性UCB（LinUCB）是解决线性情景多臂老虎机问题的一种常用算法。在时刻，LinUCB构造一个置信区间，其以很高的概率包含了未知参数。然后，该算法为决策集合中的每个决策的报酬计算一个置信区间上界（UCB），并且“乐观地”选择一个UCB最高的决策：，其中。本文假设报酬函数是线性的且带有可加的次高斯噪声，即。考虑如下的点估计：
其中，。因此，可以构造如下的置信区间：
其中，参数的选取需要依赖一定的技术性假设，具体细节可参考原文。
定理1：在一定的假设条件下，以至少的概率,算法1的遗憾值满足：
其中，
且间隔相关的遗憾值满足:
5、满足联合差分隐私的线性UCB算法
在算法1中，置信区间的构建需要基于和,其用到了时刻前历史的决策和报酬信息。本文通过对矩阵 和向量 进行扰动来实现定义2中的联合差分隐私。如果一个序列关于满足-差分隐私，那么算法1也满足-差分隐私。
定义3 灵敏度：函数的灵敏度可定义为:
在差分隐私问题中，令表示没有差分隐私要求时算法的输出函数，,其中表示Laplace噪声。那么可以通过控制，满足即可满足-差分隐私。本文通过结合文献中已有的基于树的隐私算法和线性UCB算法来解决联合差分隐私的线性情景多臂老虎机问题。
首先，将 和 组合为一个单独的矩阵。进一步地，由于，基于树的算法可以通过使用可加的噪声来保留一个关于的隐私估计，即。
定义4 Wishart 分布：假设G是一个的矩阵，矩阵的每一行是一个独立的元正态分布,那么Wishart 分布是如下维随机矩阵的概率分布：
记作。
定理2：在算法1中，令和分别为由树形隐私算法生成的服从分布的噪声，在一定的条件下，可以得到遗憾值满足：
，且间隔相关的遗憾值满足：
同样地，文章中也讨论了基于可加的高斯噪声来实现联合差分隐私的方法及其相关的理论保证。
6、数值实验
在这个数值实验中，差分隐私相关的参数，，决策次数,问题维度,决策的个数结果表明，基于高斯噪声的算法比基于Wshar噪声的方法效果更好。
引用文献
[1] Shariff R, Sheffet O. Differentially private contextual linear bandits[J]. Advances in Neural Information Processing Systems, 2018, 31.
[2] Lattimore T, Szepesvári C. Bandit algorithms[M]. Cambridge University Press, 2020.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
责任编辑：胡明杰 陈宇文
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
