我们考虑涉及一组代理的在线估计问题。每个代理都可以访问（个人）流程，该过程从实数分布中生成样本，并试图估算其平均值。我们研究了某些分布具有相同均值的情况，并且允许代理人积极查询其他代理商的信息。目的是设计一种算法，该算法使每个代理都能够通过与其他代理商进行沟通来改善其平均估计。平均值的均值和分布数量尚不清楚，这使得任务是非平凡的。我们介绍了一种新颖的协作策略，以解决这个在线个性化的平均估计问题。我们分析其时间复杂性，并引入在数值实验中享有良好性能的变体。我们还将我们的方法扩展到了具有相似手段的代理商群体寻求估算其群集的平均值的环境。

我们在多机构学习模型中调查了Top-$ m $ ARM标识，这是Bandit理论中的一个基本问题，在该模型中，代理商合作学习目标函数。我们有兴趣设计使用最低沟通成本的协作学习算法，以实现最大的加速（与单人学习算法相比），因为沟通通常是多学院学习中的瓶颈。我们提供算法和不可能的结果，并进行一组实验以证明我们的算法的有效性。

我们考虑使用个性化的联合学习，除了全球目标外，每个客户还对最大化个性化的本地目标感兴趣。我们认为，在一般连续的动作空间设置下，目标函数属于繁殖的内核希尔伯特空间。我们提出了基于替代高斯工艺（GP）模型的算法，该算法达到了最佳的遗憾顺序（要归结为各种因素）。此外，我们表明，GP模型的稀疏近似显着降低了客户之间的沟通成本。

在本文中，我们研究了时间速度与非IID数据的协作学习模型中学习过程的交流次数之间的权衡，其中多个代理与可能不同的环境互动，他们希望学习一个目标。汇总环境。我们在匪徒理论中使用一个基本问题，称为多臂匪徒中最佳ARM识别作为传递以下概念信息的工具：对非IID数据的协作学习比在IID数据上更加困难。特别是，我们显示以下内容：a）非IID数据设置中的加速度可能小于$ 1 $（即放缓）。当回合$ r = o（1）$的数量时，我们将至少需要多项式数量的代理（就武器数量而言）来实现大于$ 1 $的加速。这与IID数据设置形成鲜明对比，在$ r \ ge 2 $中，无论代理数量如何，加速度总是至少$ 1 $。 b）学习过程中的适应性无济于事。这与IID数据设置形成鲜明对比，为了实现相同的速度，最佳的非自适应算法需要比最佳自适应算法要大得多。在技​​术空间中，我们进一步开发了Arxiv：1904.03293中引入的广义消除技术。我们表明，在使用复杂的硬输入分布并直接证明自适应算法的下限时，分配类别的隐式表示非常有用。

Due mostly to its application to cognitive radio networks, multiplayer bandits gained a lot of interest in the last decade. A considerable progress has been made on its theoretical aspect. However, the current algorithms are far from applicable and many obstacles remain between these theoretical results and a possible implementation of multiplayer bandits algorithms in real cognitive radio networks. This survey contextualizes and organizes the rich multiplayer bandits literature. In light of the existing works, some clear directions for future research appear. We believe that a further study of these different directions might lead to theoretical algorithms adapted to real-world situations.

联合学习的个性化可以通过交易模型的偏差来提高用户模型的准确性（通过使用来自可能不同）的数据引入的数据来抵消其方差（由于任何单个用户的数据量有限）。为了开发最佳地平衡此权衡的培训算法，有必要扩展我们的理论基础。在这项工作中，我们将个性化协作学习问题正式，作为用户目标$ f_0（x）$的随机优化，同时获得对N $相关但其他用户的不同目标$ \ {f_1（x），\ dots，f_n （x）\} $。我们在此设置中为两个算法提供收敛保证 - 一种名称的个性化方法，称为\ emph {加权梯度平均}，以及一种新颖的\ emph {偏压校正}方法 - 以及我们可以最佳地折衷的条件偏差减少方差并实现线性加速WRT \用户数量$ N $。此外，我们还经验验证他们的表现，证实了我们的理论见解。

我们研究Stackelberg游戏，其中一位校长反复与长寿，非洋流代理商进行互动，而不知道代理商的回报功能。尽管当代理商是近视，非侧心代理会带来额外的并发症时，在Stackelberg游戏中的学习是充分理解的。尤其是，非洋流代理可以从战略上选择当前劣等的行动，以误导校长的学习算法并在未来获得更好的结果。我们提供了一个通用框架，该框架可在存在近视剂的情况下降低非洋白酶的学习来优化强大的匪徒。通过设计和分析微型反应性匪徒算法，我们的还原从校长学习算法的统计效率中进行了差异，以与其在诱导接近最佳的响应中的有效性。我们将此框架应用于Stackelberg Security Games（SSG），需求曲线，战略分类和一般有限的Stackelberg游戏的价格。在每种情况下，我们都表征了近最佳响应中存在的错误的类型和影响，并为此类拼写错误开发了一种鲁棒性的学习算法。在此过程中，我们通过最先进的$ O（n^3）$从SSGS中提高了SSG中的学习复杂性，从通过发现此类游戏的基本结构属性。该结果除了对非洋流药物学习之外，还具有独立的兴趣。

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.

在本文中，我们制定了在内核强盗问题（COPE-KB）中的协作纯探索，它为在有限的通信和一般奖励函数下提供了一种用于多智能组件多任务决策的新型模型，并且适用于许多在线学习任务，例如，推荐系统和网络调度。我们考虑两个COPE-KB，即固定信道（FC）和固定预算（FB）的设置，以及设计两个最佳算法COOPKERNECC（FC）和Coopkerhelfb（FB）。我们的算法配备了创新和高效的核化估计，同时实现了计算和通信效率。建立统计和通信度量标准下的上限和下限以证明我们算法的最优性。理论界限成功地量化了任务相似性对学习加速度的影响，并且只取决于内核特征空间的有效维度。我们的分析技术，包括数据尺寸分解，线性结构化实例转换和（通信）圆形加速感应，是新颖的，适用于其他强盗问题。提供了实证评估以验证我们的理论结果，并展示我们算法的性能优势。

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

在线学习环境（即联合学习（FL））中，合作学习范式的迅速增加。与大多数FL设置不同，在许多情况下，代理商具有竞争力。每个代理商都想向他人学习，但是它为他人分享的信息的一部分可能很敏感。因此，它希望其隐私。这项工作调查了一组代理人同时工作，以解决类似的组合匪徒问题，同时保持质量约束。这些代理商可以通过使用差异隐私来保密其敏感信息的同时学习敏感信息吗？我们观察到交流可以减少遗憾。但是，保护敏感信息的差异隐私技术使数据嘈杂，并且可能会恶化，而不是帮助改善遗憾。因此，我们注意到，必须决定何时交流以及学习哪些共享数据以学会在遗憾和隐私之间取得功能平衡。对于这样的联合组合MAB设置，我们提出了一个保护隐私的联合联合组合匪徒，P-FCB。我们通过模拟说明了P-FCB的功效。我们进一步表明，我们的算法在遗憾方面提供了改善，同时维护质量阈值和有意义的隐私保证。

大多数在线平台都在努力从与用户的互动中学习，许多人从事探索：为了获取新信息而做出潜在的次优选择。我们研究探索与竞争之间的相互作用：这样的平台如何平衡学习探索和用户的竞争。在这里，用户扮演三个不同的角色：他们是产生收入的客户，他们是学习的数据来源，并且是自私的代理商，可以在竞争平台中进行选择。我们考虑了一种风格化的双重垄断模型，其中两家公司面临着相同的多军强盗问题。用户一一到达，并在两家公司之间进行选择，因此，只有在选择它的情况下，每个公司都在其强盗问题上取得进展。通过理论结果和数值模拟的混合，我们研究了竞争是否会激发更好的Bandit算法的采用，以及它是否导致用户增加福利。我们发现，Stark竞争会导致公司致力于导致低福利的“贪婪”强盗算法。但是，通过向公司提供一些“免费”用户来激励更好的探索策略并增加福利来削弱竞争。我们调查了削弱竞争的两个渠道：放松用户的理性并为一家公司带来首次推广优势。我们的发现与“竞争与创新”关系密切相关，并阐明了数字经济中的第一步优势。

在线强化学习（RL）中的挑战之一是代理人需要促进对环境的探索和对样品的利用来优化其行为。无论我们是否优化遗憾，采样复杂性，状态空间覆盖范围或模型估计，我们都需要攻击不同的勘探开发权衡。在本文中，我们建议在分离方法组成的探索 - 剥削问题：1）“客观特定”算法（自适应）规定哪些样本以收集到哪些状态，似乎它可以访问a生成模型（即环境的模拟器）; 2）负责尽可能快地生成规定样品的“客观无关的”样品收集勘探策略。建立最近在随机最短路径问题中进行探索的方法，我们首先提供一种算法，它给出了每个状态动作对所需的样本$ B（S，a）$的样本数量，需要$ \ tilde {o} （bd + d ^ {3/2} s ^ 2 a）收集$ b = \ sum_ {s，a} b（s，a）$所需样本的$时间步骤，以$ s $各国，$ a $行动和直径$ d $。然后我们展示了这种通用探索算法如何与“客观特定的”策略配对，这些策略规定了解决各种设置的样本要求 - 例如，模型估计，稀疏奖励发现，无需无成本勘探沟通MDP - 我们获得改进或新颖的样本复杂性保证。

We study the best-arm identification problem in multi-armed bandits with stochastic, potentially private rewards, when the goal is to identify the arm with the highest quantile at a fixed, prescribed level. First, we propose a (non-private) successive elimination algorithm for strictly optimal best-arm identification, we show that our algorithm is $\delta$-PAC and we characterize its sample complexity. Further, we provide a lower bound on the expected number of pulls, showing that the proposed algorithm is essentially optimal up to logarithmic factors. Both upper and lower complexity bounds depend on a special definition of the associated suboptimality gap, designed in particular for the quantile bandit problem, as we show when the gap approaches zero, best-arm identification is impossible. Second, motivated by applications where the rewards are private, we provide a differentially private successive elimination algorithm whose sample complexity is finite even for distributions with infinite support-size, and we characterize its sample complexity. Our algorithms do not require prior knowledge of either the suboptimality gap or other statistical information related to the bandit problem at hand.

级别设置估计问题旨在查找域$ {\ cal x} $的所有点，其中一个未知函数$ f：{\ cal x} \ lightarrow \ mathbb {r} $超过阈值$ \ alpha $ 。估计基于可以在$ {\ cal x} $中顺序和自适应地选择的位置获取的嘈杂函数评估。阈值$ \ alpha $可以是\弹性{显式}，并提供先验，或\ \ ich {隐式}，相对于最佳函数值定义，即$ \ alpha =（1- \ epsilon）f（x_ \ AST）$关于给定$ \ epsilon> 0 $ why $ f（x_ \ ist）$是最大函数值，并且未知。在这项工作中，我们通过将其与最近的自适应实验设计方法相关联，为近期自适应实验设计方法提供了一种新的再现内核盗窃空间（RKHS）设置。我们假设可以通过RKHS中的函数近似于未知的拼写，并为此设置中隐含和显式案件提供新的算法，具有很强的理论保证。此外，在线性（内核）设置中，我们表明我们的界限几乎是最佳的，即，我们的上限与阈值线性匪徒的现有下限匹配。据我们所知，这项工作提供了第一个实例依赖性非渐近的上限，就匹配信息理论下限的水平设定估计的样本复杂性。

We consider distributed linear bandits where $M$ agents learn collaboratively to minimize the overall cumulative regret incurred by all agents. Information exchange is facilitated by a central server, and both the uplink and downlink communications are carried over channels with fixed capacity, which limits the amount of information that can be transmitted in each use of the channels. We investigate the regret-communication trade-off by (i) establishing information-theoretic lower bounds on the required communications (in terms of bits) for achieving a sublinear regret order; (ii) developing an efficient algorithm that achieves the minimum sublinear regret order offered by centralized learning using the minimum order of communications dictated by the information-theoretic lower bounds. For sparse linear bandits, we show a variant of the proposed algorithm offers better regret-communication trade-off by leveraging the sparsity of the problem.

Data depth, introduced by Tukey (1975), is an important tool in data science, robust statistics, and computational geometry. One chief barrier to its broader practical utility is that many common measures of depth are computationally intensive, requiring on the order of $n^d$ operations to exactly compute the depth of a single point within a data set of $n$ points in $d$-dimensional space. Often however, we are not directly interested in the absolute depths of the points, but rather in their \textit{relative ordering}. For example, we may want to find the most central point in a data set (a generalized median), or to identify and remove all outliers (points on the fringe of the data set with low depth). With this observation, we develop a novel and instance-adaptive algorithm for adaptive data depth computation by reducing the problem of exactly computing $n$ depths to an $n$-armed stochastic multi-armed bandit problem which we can efficiently solve. We focus our exposition on simplicial depth, developed by \citet{liu1990notion}, which has emerged as a promising notion of depth due to its interpretability and asymptotic properties. We provide general instance-dependent theoretical guarantees for our proposed algorithms, which readily extend to many other common measures of data depth including majority depth, Oja depth, and likelihood depth. When specialized to the case where the gaps in the data follow a power law distribution with parameter $\alpha<2$, we show that we can reduce the complexity of identifying the deepest point in the data set (the simplicial median) from $O(n^d)$ to $\tilde{O}(n^{d-(d-1)\alpha/2})$, where $\tilde{O}$ suppresses logarithmic factors. We corroborate our theoretical results with numerical experiments on synthetic data, showing the practical utility of our proposed methods.

本文介绍了信息性多臂强盗（IMAB）模型，在每个回合中，玩家选择手臂，观察符号，并以符号的自我信息形式获得未观察到的奖励。因此，手臂的预期奖励是产生其符号的源质量函数的香农熵。玩家的目标是最大程度地提高与武器的熵值相关的预期奖励。在假设字母大小是已知的假设下，为IMAB模型提出了两种基于UCB的算法，该算法考虑了插件熵估计器的偏差。第一种算法在熵估计中乐观地纠正了偏置项。第二算法依赖于数据依赖性置信区间，该置信区间适应具有较小熵值的源。性能保证是通过上限为每种算法的预期遗憾提供的。此外，在Bernoulli案例中，将这些算法的渐近行为与伪遗憾的Lai-Robbins的下限进行了比较。此外，在假设\ textit {cract}字母大小的假设下是未知的，而播放器仅知道其上方的宽度上限，提出了一种基于UCB的算法，在其中，玩家的目的是减少由该算法造成的遗憾。未知的字母尺寸在有限的时间方面。数字结果说明了论文中介绍的算法的预期遗憾。

我们提出了置信度序列 - 置信区间序列，其均匀地随时间均匀 - 用于基于I.I.D的流的完整，完全有序集中的任何分布的量级。观察。我们提供用于跟踪固定定量的方法并同时跟踪所有定量。具体而言，我们提供具有小常数的明确表达式，其宽度以尽可能快的$ \ SQRT {t} \ log \ log t} $率，以及实证分布函数的非渐近浓度不等式以相同的速率均匀地持续持续。后者加强了Smirnov迭代对数的实证过程法，延长了DVORETZKY-KIEFER-WOLFOITZ不等式以均匀地保持一段时间。我们提供了一种新的算法和样本复杂性，用于在多武装强盗框架中选择具有大约最佳定量的臂。在仿真中，我们的方法需要比现有方法更少五到五十的样品。

联邦学习（FL）是大规模分布式学习的范例，它面临两个关键挑战：（i）从高度异构的用户数据和（ii）保护参与用户的隐私的高效培训。在这项工作中，我们提出了一种新颖的流动方法（DP-SCaffold）来通过将差异隐私（DP）约束结合到流行的脚手架算法中来解决这两个挑战。我们专注于有挑战性的环境，用户在没有任何可信中介的情况下与“诚实但奇怪的”服务器沟通，这需要确保隐私不仅可以访问最终模型的第三方，而且还要对服务器观察所有用户通信。使用DP理论的高级结果，我们建立了凸面和非凸面目标算法的融合。我们的分析清楚地突出了数据异质性下的隐私式折衷，并且当局部更新的数量和异质性水平增长时，展示了在最先进的算法DP-Fedivg上的DP-Scaffold的优越性。我们的数值结果证实了我们的分析，并表明DP-Scaffold在实践中提供了重大的收益。