上下文强盗算法广泛用于域中，其中期望通过利用上下文信息提供个性化服务，这可能包含需要保护的敏感信息。灵感来自这种情况，我们研究了差异隐私（DP）约束的上下文线性强盗问题。虽然文献专注于集中式（联合DP）或本地（本地DP）隐私，但我们考虑了隐私的洗牌模型，我们表明可以在JDP和LDP之间实现隐私/实用权折衷。通过利用隐私和批处理从匪徒进行洗牌，我们介绍了一个遗憾的遗留率$ \ widetilde {\ mathcal {o}}（t ^ {2/3} / \ varepsilon ^ {1/3}）$，同时保证中央（联合）和当地隐私。我们的结果表明，通过利用Shuffle模型在保留本地隐私时，可以在JDP和LDP之间获得权衡。

本文研究了Markov决策过程（MDP）的隐私保留探索，线性表示。我们首先考虑线性混合MDP（Ayoub等，2020）（A.K.A.基于模型的设置）的设置，并提供统一的框架，用于分析关节和局部差异私有（DP）探索。通过这个框架，我们证明了一个$ \ widetilde {o}（k ^ {3/4} / \ sqrt {\ epsilon}）$遗憾绑定$（\ epsilon，\ delta）$ - 本地DP探索和$ \widetilde {o}（\ sqrt {k / \ epsilon}）$后悔绑定$（\ epsilon，\ delta）$ - 联合dp。我们进一步研究了Linear MDP中的隐私保留探索（Jin等，2020）（AKA \ Forws-Free Setting），我们提供$ \ widetilde {o}（\ sqrt {k / \ epsilon}）$后悔绑定$（\ epsilon，\ delta）$ - 关节dp，具有基于低切换的新型算法。最后，我们提供了在这种无模型设置中设计本地DP算法的问题的见解。

在本文中，我们仅使用部分分布式反馈来研究全球奖励最大化的问题。这个问题是由几个现实世界应用程序（例如蜂窝网络配置，动态定价和政策选择）激发的，其中中央实体采取的行动会影响有助于全球奖励的大量人群。但是，从整个人群那里收集此类奖励反馈不仅会产生高昂的成本，而且经常导致隐私问题。为了解决此问题，我们考虑了差异的私有分布式线性土匪，其中只选择了来自人群的一部分用户（称为客户）来参与学习过程，并且中央服务器通过迭代地汇总这些部分从这种部分反馈中学习了全局模型客户的本地反馈以差异化的方式。然后，我们提出了一个统一的算法学习框架，称为差异性分布式分布式消除（DP-DPE），该框架可以与流行的差异隐私（DP）模型（包括中央DP，Local DP，Local DP和Shuffle DP）自然集成。此外，我们证明DP-DPE既可以达到统一的遗憾，又实现了额定性沟通成本。有趣的是，DP-DPE也可以“免费”获得隐私保护，这是因为由于隐私保证是一个较低的加法术语。此外，作为我们技术的副产品，对于标准的差异私有线性匪徒，也可以实现“自由”隐私的相同结果。最后，我们进行模拟以证实我们的理论结果并证明DP-DPE的有效性。

我们考虑在差异隐私（DP）的分布式信任模型下考虑标准的$ k $武装匪徒问题，该问题使得无需可信赖的服务器保证隐私。在此信任模型下，先前的工作主要集中在使用Shuffle协议实现隐私，在此过程中，在发送到中央服务器之前，将一批用户数据随机排列。通过牺牲额外的添加剂$ o \！\ left（\！\ frac {k \ log t \ sqrt {\ log（1/\ delta）}} } {\ epsilon} \！\ right）\！$在$ t $ - 步骤累积遗憾中成本。相比之下，在广泛使用的中央信托模型下实现更强（$ \ epsilon，0 $）或纯dp保证的最佳隐私成本仅为$ \ theta \！\ left（\！\ frac {k \ log t t t } {\ epsilon} \！\ right）\！$，但是，需要一个受信任的服务器。在这项工作中，我们旨在获得分布式信托模型下的纯DP保证，同时牺牲比中央信托模型的遗憾。我们通过基于连续的ARM消除设计通用的匪徒算法来实现这一目标，在这种情况下，通过使用安全的计算协议确保使用等效的离散拉普拉斯噪声来损坏奖励来保证隐私。我们还表明，当使用Skellam噪声和安全协议实例化时，我们的算法可确保\ emph {r \'{e} nyi差异隐私} - 一个比分布式信任模型的近似dp更强的概念$ o \！\ left（\！\ frac {k \ sqrt {\ log t}}}} {\ epsilon} \！\ right）\！$。

在本文中，我们提出了针对中央，局部和洗牌模型中随机线性匪徒问题的差异私有算法。在中心模型中，我们获得了与最佳非私有算法的遗憾，这意味着我们可以免费获得隐私。特别是，我们感到遗憾的是$ \ tilde {o}（\ sqrt {t}+\ frac {1} {\ epsilon}）$匹配已知的私有线性匪徒的较低限制，而最佳以前已知的算法实现了$ \ tilde {o}（\ frac {1} {\ epsilon} \ sqrt {t}）$。在当地情况下，我们感到遗憾的是$ \ tilde {o}（\ frac {1} {\ epsilon} {\ sqrt {t}} $，与常数$ \ epsilon $相匹配的非私人遗憾，但是当$ \ epsilon $很小时，会受到遗憾的处罚。在洗牌模型中，我们还遗憾地对$ \ tilde {o}（\ sqrt {t}+\ frac {1} {\ epsilon} {\ epsilon}）$％$ \ epsilon $，如中心案例，而最佳情况是以前已知的算法对$ \ tilde {o}（\ frac {1} {\ epsilon} {t^{3/5}}）$感到遗憾。我们的数值评估验证了我们的理论结果。

我们研究依靠敏感数据（例如医疗记录）的环境的顺序决策中，研究隐私的探索。特别是，我们专注于解决在线性MDP设置中受（联合）差异隐私的约束的增强学习问题（RL），在该设置中，动态和奖励均由线性函数给出。由于Luyo等人而引起的此问题的事先工作。 （2021）实现了$ o（k^{3/5}）$的依赖性的遗憾率。我们提供了一种私人算法，其遗憾率提高，最佳依赖性为$ o（\ sqrt {k}）$对情节数量。我们强烈遗憾保证的关键配方是策略更新时间表中的适应性，其中仅在检测到数据足够更改时才发生更新。结果，我们的算法受益于低切换成本，并且仅执行$ o（\ log（k））$更新，这大大降低了隐私噪声的量。最后，在最普遍的隐私制度中，隐私参数$ \ epsilon $是一个常数，我们的算法会造成可忽略不计的隐私成本 - 与现有的非私人遗憾界限相比，由于隐私而引起的额外遗憾在低阶中出现了术语。

我们研究了批量线性上下文匪徒的最佳批量遗憾权衡。对于任何批次数$ M $，操作次数$ k $，时间范围$ t $和维度$ d $，我们提供了一种算法，并证明了其遗憾的保证，这是由于技术原因，具有两阶段表达作为时间的时间$ t $ grose。我们还证明了一个令人奇迹的定理，令人惊讶地显示了在问题参数的“问题参数”中的两相遗憾（最高〜对数因子）的最优性，因此建立了确切的批量后悔权衡。与最近的工作\ citep {ruan2020linear}相比，这表明$ m = o（\ log \ log t）$批次实现无需批处理限制的渐近最佳遗憾的渐近最佳遗憾，我们的算法更简单，更易于实际实现。此外，我们的算法实现了所有$ t \ geq d $的最佳遗憾，而\ citep {ruan2020linear}要求$ t $大于$ d $的不切实际的大多项式。沿着我们的分析，我们还证明了一种新的矩阵集中不平等，依赖于他们的动态上限，这是我们的知识，这是其文学中的第一个和独立兴趣。

土匪算法已成为交互式建议的参考解决方案。但是，由于这种算法直接与用户进行改进的建议，因此对其实际使用提出了严重的隐私问题。在这项工作中，我们通过基于树的机制提出了一种差异性的线性上下文匪徒算法，以将拉普拉斯或高斯噪声添加到模型参数中。我们的关键见解是，随着模型在在线更新过程中收敛时，其参数的全局灵敏度随着时间的推移而缩小（因此命名为动态全局灵敏度）。与现有解决方案相比，我们动态的全球敏感性分析使我们能够减少噪声以获得$（\ epsilon，\ delta）$ - 差异隐私，并具有$ \ tilde o（\ log {t} \ sqrt中的噪声注入引起的额外遗憾） {t}/\ epsilon）$。我们通过动态全局灵敏度和我们提出的算法的相应上后悔界限提供了严格的理论分析。合成和现实世界数据集的实验结果证实了该算法对现有解决方案的优势。

我们考虑一个多武装的强盗设置，在每一轮的开始时，学习者接收嘈杂的独立，并且可能偏见，\ emph {评估}每个臂的真正奖励，它选择$ k $武器的目标累积尽可能多的奖励超过$ $ rounds。在假设每轮在每个臂的真正奖励从固定分发中汲取的，我们得出了不同的算法方法和理论保证，具体取决于评估的生成方式。首先，在观察功能是真正奖励的遗传化线性函数时，我们在一般情况下展示$ \ widetilde {o}（t ^ {2/3}）$后悔。另一方面，当观察功能是真正奖励的嘈杂线性函数时，我们就可以派生改进的$ \ widetilde {o}（\ sqrt {t}）$后悔。最后，我们报告了一个实证验证，确认我们的理论发现，与替代方法进行了彻底的比较，并进一步支持在实践中实现这一环境的兴趣。

在差异隐私（DP）的约束下，我们在有限地域表格马尔可夫决策过程（MDP）中研究了遗憾最小化。这是由强化学习（RL）在现实世界顺序决策中的广泛应用程序的推动，保护用户敏感和私人信息变得最大程度。我们考虑了两种DP - 关节DP（JDP）的变体，其中集中式代理负责保护用户的敏感数据和本地DP（LDP），其中需要直接在用户端保护信息。我们首先提出了两个一般框架 - 一个用于策略优化，另一个用于迭代 - 用于设计私有，乐观的RL算法。然后，我们将这些框架实例化了合适的隐私机制来满足JDP和LDP要求，并同时获得Sublinear遗憾担保。遗憾的界限表明，在JDP下，隐私费用只是较低的秩序添加剂项，而在LDP下，对于更强的隐私保护，遭受的成本是乘法的。最后，通过统一的分析获得了遗憾范围，我们相信，我们相信，可以超出表格MDP。

差异化（DP）随机凸优化（SCO）在可信赖的机器学习算法设计中无处不在。本文研究了DP-SCO问题，该问题是从分布中采样并顺序到达的流媒体数据。我们还考虑了连续发布模型，其中与私人信息相关的参数已在每个新数据（通常称为在线算法）上更新和发布。尽管已经开发了许多算法，以实现不同$ \ ell_p $ norm几何的最佳多余风险，但是没有一个现有的算法可以适应流和持续发布设置。为了解决诸如在线凸优化和隐私保护的挑战，我们提出了一种在线弗兰克 - 沃尔夫算法的私人变体，并带有递归梯度，以减少差异，以更新和揭示每个数据上的参数。结合自适应差异隐私分析，我们的在线算法在线性时间中实现了最佳的超额风险，当$ 1 <p \ leq 2 $和最先进的超额风险达到了非私人较低的风险时，当$ 2 <p \ p \ $ 2 <p \ leq \ infty $。我们的算法也可以扩展到$ p = 1 $的情况，以实现几乎与维度无关的多余风险。虽然先前的递归梯度降低结果仅在独立和分布的样本设置中才具有理论保证，但我们在非平稳环境中建立了这样的保证。为了展示我们方法的优点，我们设计了第一个DP算法，用于具有对数遗憾的高维广义线性土匪。使用多种DP-SCO和DP-Bandit算法的比较实验表现出所提出的算法的功效和实用性。

We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega(\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.

我们通过审查反馈重复进行一定的第一价格拍卖来研究在线学习，在每次拍卖结束时，出价者只观察获胜的出价，学会了适应性地出价，以最大程度地提高她的累积回报。为了实现这一目标，投标人面临着一个具有挑战性的困境：如果她赢得了竞标 - 获得正收益的唯一方法 - 然后她无法观察其他竞标者的最高竞标，我们认为我们认为这是从中汲取的。一个未知的分布。尽管这一困境让人联想到上下文强盗中的探索探索折衷权，但现有的UCB或汤普森采样算法无法直接解决。在本文中，通过利用第一价格拍卖的结构属性，我们开发了第一个实现$ o（\ sqrt {t} \ log^{2.5} t）$ hearry bund的第一个学习算法（\ sqrt {t} \ log^{2.5} t），这是最小值的最低$ $ \ log $因素，当投标人的私人价值随机生成时。我们这样做是通过在一系列问题上提供算法，称为部分有序的上下文匪徒，该算法将图形反馈跨动作，跨环境跨上下文进行结合，以及在上下文中的部分顺序。我们通过表现出一个奇怪的分离来确定该框架的优势和劣势，即在随机环境下几乎可以独立于动作/背景规模的遗憾，但是在对抗性环境下是不可能的。尽管这一通用框架有限制，但我们进一步利用了第一价格拍卖的结构，并开发了一种学习算法，该算法在存在对手生成的私有价值的情况下，在存在的情况下可以有效地运行样本（并有效地计算）。我们建立了一个$ o（\ sqrt {t} \ log^3 t）$遗憾，以此为此算法，因此提供了对第一价格拍卖的最佳学习保证的完整表征。

We study distributed contextual linear bandits with stochastic contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features over the course of $T$ rounds. For this problem, we derive the first ever information-theoretic lower bound $\Omega(dN)$ on the communication cost of any algorithm that performs optimally in a regret minimization setup. We then propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that the communication cost of DisBE-LUCB matches our lower bound up to logarithmic factors. In particular, for scenarios with known context distribution, the communication cost of DisBE-LUCB is only $\tilde{\mathcal{O}}(dN)$ and its regret is ${\tilde{\mathcal{O}}}(\sqrt{dNT})$, which is of the same order as that incurred by an optimal single-agent algorithm for $NT$ rounds. We also provide similar bounds for practical settings where the context distribution can only be estimated. Therefore, our proposed algorithm is nearly minimax optimal in terms of \emph{both regret and communication cost}. Finally, we propose DecBE-LUCB, a fully decentralized version of DisBE-LUCB, which operates without a central server, where agents share information with their \emph{immediate neighbors} through a carefully designed consensus procedure.

我们介绍了一个多臂强盗模型，其中奖励是多个随机变量的总和，每个动作只会改变其中的分布。每次动作之后，代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的，在该系统中，变量代表单个客户的结果，例如点击。我们提出了UCB风格的算法，以估计基线上的动作的提升。我们研究了问题的多种变体，包括何时未知基线和受影响的变量，并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限，以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。

In this paper, we address the stochastic contextual linear bandit problem, where a decision maker is provided a context (a random set of actions drawn from a distribution). The expected reward of each action is specified by the inner product of the action and an unknown parameter. The goal is to design an algorithm that learns to play as close as possible to the unknown optimal policy after a number of action plays. This problem is considered more challenging than the linear bandit problem, which can be viewed as a contextual bandit problem with a \emph{fixed} context. Surprisingly, in this paper, we show that the stochastic contextual problem can be solved as if it is a linear bandit problem. In particular, we establish a novel reduction framework that converts every stochastic contextual linear bandit instance to a linear bandit instance, when the context distribution is known. When the context distribution is unknown, we establish an algorithm that reduces the stochastic contextual instance to a sequence of linear bandit instances with small misspecifications and achieves nearly the same worst-case regret bound as the algorithm that solves the misspecified linear bandit instances. As a consequence, our results imply a $O(d\sqrt{T\log T})$ high-probability regret bound for contextual linear bandits, making progress in resolving an open problem in (Li et al., 2019), (Li et al., 2021). Our reduction framework opens up a new way to approach stochastic contextual linear bandit problems, and enables improved regret bounds in a number of instances including the batch setting, contextual bandits with misspecifications, contextual bandits with sparse unknown parameters, and contextual bandits with adversarial corruption.

我们研究$ k $ used的上下文决斗强盗问题，一个顺序决策制定设置，其中学习者使用上下文信息来制作两个决定，但只观察到\ emph {基于优先级的反馈}建议一个决定比另一个决定更好。我们专注于可实现的遗憾最小化问题，其中反馈由一个由给定函数类$ \ mathcal f $规定的成对偏好矩阵生成。我们提供了一种新的算法，实现了最佳反应遗憾的新概念的最佳遗憾，这是一个严格更强烈的性能测量，而不是先前作品所考虑的绩效衡量标准。该算法还在计算上有效，在多项式时间中运行，假设访问在线丢失回归超过$ \ mathcal f $。这可以解决dud \'ik等人的开放问题。[2015]关于Oracle高效，后悔 - 用于上下文决斗匪徒的最佳算法。

我们研究了具有$ \ epsilon $ -Global差异隐私（DP）的多臂土匪的问题。首先，我们证明了使用$ \ epsilon $ -Global DP量化土匪硬度的随机和线性土匪的最小值和问题依赖的后悔下限。这些界限表明存在两个硬度制度，具体取决于隐私预算$ \ epsilon $。在高私人制度（小$ \ epsilon $）中，硬度取决于隐私的耦合效果以及有关奖励分布的部分信息。在低私人制度（大$ \ epsilon $）中，具有$ \ epsilon $ -Global DP的土匪并不比没有隐私的土匪更难。对于随机匪徒，我们进一步提出了一个通用框架，以设计基于索引的乐观强盗算法的近乎最佳的$ \ epsilon $全局DP扩展。该框架由三种成分组成：拉普拉斯机制，依赖手臂的自适应发作以及仅在最后一集中收集的奖励来计算私人统计数据。具体而言，我们实例化了UCB和KL-UCB算法的Epsilon $ -Global DP扩展，即ADAP-UCB和ADAP-KLUCB。 Adap-klucb是两者都满足$ \ epsilon $ -Global DP的第一种算法，并产生了遗憾的上限，与问题依赖性下限与乘法常数相匹配。

上下文多臂强盗（MAB）是推荐系统中重要的顺序决策问题。一系列称为土匪（俱乐部）聚集的作品，利用了对用户的协作效果，并显着提高了建议质量。由于应用程序量表的日益增加和对隐私的关注，因此需求不断增加，以使用户数据分散并将匪徒学习推向本地服务器端。但是，现有的俱乐部算法是在中央服务器上可用的集中设置下设计的。我们专注于研究Bandit（FCLUB）问题的联合在线聚类，该问题旨在最大程度地减少遗憾，同时满足隐私和沟通的考虑。我们为群集检测设计了一种新的基于阶段的方案，并为解决此问题的合作强盗学习提供了一种新型的异步通信协议。为了保护用户的隐私，以前的差异隐私（DP）定义不是很合适，我们提出了一个在用户群集级别上起作用的新DP概念。我们提供了严格的证据，以证明我们的算法同时实现（聚类）DP，sublrinear沟通复杂性和sublrinear遗憾。最后，实验评估表明，与基准算法相比，我们的表现出色。

分析若干缔约方拥有的数据，同时在效用和隐私之间实现良好的权衡是联邦学习和分析的关键挑战。在这项工作中，我们介绍了一种新颖的差异隐私（LDP）的放松，自然地出现在完全分散的算法中，即，当参与者通过沿着网络图的边缘传播没有中央协调员的边缘交换信息时。我们呼叫网络DP的这种放松捕获了用户只有系统的本地视图。为了展示网络DP的相关性，我们研究了一个分散的计算模型，其中令牌在网络图上执行散步，并由接收它的方顺序更新。对于诸如实际求和，直方图计算和具有梯度下降的优化等任务，我们提出了在环和完整拓扑上的简单算法。我们证明，网络DP下我们算法的隐私式实用权折衷显着提高了LDP下可实现的内容（有时甚至与可信赖的策展人模型的效用）的可实现，首次显示正式隐私收益可以从中获得完全分散。我们的实验说明了通过随机梯度下降的分散训练方法的改进效用。