我们应对在分布式环境中学习内核上下文匪徒的沟通效率挑战。尽管最近的沟通效率分布式强盗学习取得了进步，但现有的解决方案仅限于简单的模型，例如多臂匪徒和线性匪徒，这阻碍了其实用性。在本文中，我们没有假设存在从功能到预期奖励的线性奖励映射，而是通过让代理商在复制的内核希尔伯特（RKHS）中协作搜索来考虑非线性奖励映射。由于分布式内核学习需要传输原始数据，因此引入了沟通效率的重大挑战，从而导致沟通成本增长线性W.R.T.时间范围$ t $。我们通过装备所有代理通过通用的nystr \“ {o} m嵌入，随着收集更多的数据点的收集。我们严格地证明我们的算法可以以遗憾和通信成本达到次线性率，我们可以通过适应性更新的嵌入来解决这个问题。 。

我们研究联合的上下文线性匪徒，其中$ m $代理相互合作，在中央服务器的帮助下解决全球上下文线性匪徒问题。我们考虑了异步设置，所有代理商都独立工作，一个代理和服务器之间的通信不会触发其他代理的通信。我们提出了一种基于乐观原理的简单算法\ texttt {fedlinucb}。我们证明\ texttt {fedlinucb}的遗憾是由$ \ tilde {o}（d \ sqrt {\ sum_ {m = 1}^m t_m}）$界定的，通信复杂性是$ \ tilde {o}（o}（o}（o}（o}（o））dm^2）$，其中$ d $是上下文向量的尺寸，$ t_m $是与环境的交互总数，$ m $ -th代理。据我们所知，这是第一种可证明有效的算法，它允许联合上下文线性匪徒完全异步通信，同时获得与单一代理设置相同的遗憾保证。

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

我们研究了带有未知上下文的分布式随机多臂上下文匪徒的问题，其中M代理商在中央服务器的协调下合作选择最佳动作，以最大程度地减少遗憾。在我们的模型中，对手选择在可能的上下文集上的分布，而代理只观察到上下文分布，而确切的上下文是代理人未知的。例如，当上下文本身是嘈杂的测量或基于天气预报或股票市场预测中的预测机制时，就会出现这种情况。我们的目标是开发一种分布式算法，该算法选择一系列最佳动作序列以最大程度地提高累积奖励。通过执行功能向量转换并利用UCB算法，我们提出了一种具有上下文分布的随机匪徒的UCB算法，并证明我们的算法实现了$ O（D \ sqrt {mt} log^2t log^2t）$ o的遗憾和通信范围对于线性参数化的奖励函数，分别为$ o（m^{1.5} d^3）$。我们还考虑了一种情况，代理在选择动作后会观察实际情况。对于此设置，我们提出了一种修改后的算法，该算法利用其他信息来实现更严格的遗憾。最后，我们验证了算法的性能，并使用有关合成数据和现实世界Movielens数据集的大量模拟将其与其他基线方法进行了比较。

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

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.

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.

我们研究了与中央服务器和多个客户的联合学习多臂强盗设置中最佳手臂识别的问题。每个客户都与多臂强盗相关联，其中每个手臂在具有未知均值和已知方差的高斯分布之后，每个手臂都能产生{\ em I.i.d。} \奖励。假定所有客户的武器集相同。我们定义了两个最佳手臂的概念 - 本地和全球。客户的当地最好的手臂是客户本地手臂中最大的手臂，而全球最佳手臂是所有客户平均平均值最大的手臂。我们假设每个客户只能从当地的手臂上观察奖励，从而估计其当地最好的手臂。客户在上行链路上与中央服务器进行通信，该上行链路需要每个上行链路的使用费用为$ C \ ge0 $单位。在服务器上估算了全球最佳手臂。目的是确定当地最佳武器和全球最佳臂，总成本最少，定义为所有客户的ARM选择总数和总通信成本的总和，但在错误概率上取决于上限。我们提出了一种基于连续消除的新型算法{\ sc fedelim}，仅在指数时间步骤中进行通信，并获得高概率依赖性实例依赖性上限，以其总成本。我们论文的关键要点是，对于任何$ c \ geq 0 $，错误概率和错误概率足够小，{\ sc fedelim}下的ARM选择总数（分别为\ the总费用）最多为〜$ 2 $（reves 。〜 $ 3 $）乘以其在每个时间步骤中通信的变体下的ARM选择总数的最大总数。此外，我们证明后者在期望最高的恒定因素方面是最佳的，从而证明{\ sc fedelim}中的通信几乎是无成本的。我们从数值验证{\ sc fedelim}的功效。

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

我们考虑基于嘈杂的强盗反馈优化黑盒功能的问题。内核强盗算法为此问题显示了强大的实证和理论表现。然而，它们严重依赖于模型所指定的模型，并且没有它可能会失败。相反，我们介绍了一个\ emph {isspecified}内塞的强盗设置，其中未知函数可以是$ \ epsilon $ - 在一些再现内核希尔伯特空间（RKHS）中具有界限范数的函数均匀近似。我们设计高效实用的算法，其性能在模型误操作的存在下最微小地降低。具体而言，我们提出了一种基于高斯过程（GP）方法的两种算法：一种乐观的EC-GP-UCB算法，需要了解误操作误差，并相断的GP不确定性采样，消除型算法，可以适应未知模型拼盘。我们在$ \ epsilon $，时间范围和底层内核方面提供累积遗憾的上限，我们表明我们的算法达到了$ \ epsilon $的最佳依赖性，而没有明确的误解知识。此外，在一个随机的上下文设置中，我们表明EC-GP-UCB可以有效地与遗憾的平衡策略有效地结合，尽管不知道$ \ epsilon $尽管不知道，但仍然可以获得类似的遗憾范围。

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

汤普森采样（TS）是解决上下文多武装强盗问题最有效的算法之一。在本文中，我们提出了一种新的算法，称为神经汤普森采样，这适应了深度神经网络，用于勘探和剥削。在我们的算法的核心是一种新的奖励的后分布，其平均值是神经网络近似器，并且其方差建立在相应神经网络的神经切线特征上。我们证明，如果底层奖励函数是有界的，则可以保证所提出的算法来实现$ \ mathcal {o}（t ^ {1/2}）$的累积遗憾，它与其他上下文强盗算法的遗憾匹配总轮数量$ t $。各种数据集中其他基准强盗算法的实验比较证实了我们的理论。

我们为线性上下文匪徒提出了一种新颖的算法（\ sqrt {dt \ log t}）$遗憾，其中$ d $是上下文的尺寸，$ t $是时间范围。我们提出的算法配备了一种新型估计量，其中探索通过显式随机化嵌入。根据随机化的不同，我们提出的估计器从所有武器的上下文或选定的上下文中都取得了贡献。我们为我们的估计器建立了一个自称的绑定，这使累积遗憾的新颖分解为依赖添加剂的术语而不是乘法术语。在我们的问题设置下，我们还证明了$ \ omega（\ sqrt {dt}）$的新颖下限。因此，我们提出的算法的遗憾与对数因素的下限相匹配。数值实验支持理论保证，并表明我们所提出的方法的表现优于现有的线性匪徒算法。

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

我们研究了具有线性函数近似增强学习中的随机最短路径（SSP）问题，其中过渡内核表示为未知模型的线性混合物。我们将此类别的SSP问题称为线性混合物SSP。我们提出了一种具有Hoeffding-type置信度的新型算法，用于学习线性混合物SSP，可以获得$ \ tilde {\ Mathcal {o}}}}（d B _ {\ star}^{1.5} \ sqrt {k/c_ {k/c_ {k/c_ {k/c_ { \ min}}）$遗憾。这里$ k $是情节的数量，$ d $是混合模型中功能映射的维度，$ b _ {\ star} $限制了最佳策略的预期累积成本，$ c _ {\ min}>> 0 $是成本函数的下限。当$ c _ {\ min} = 0 $和$ \ tilde {\ mathcal {o}}}（k^{2/3}）$遗憾时，我们的算法也适用于情况。据我们所知，这是第一个具有sublrinear遗憾保证线性混合物SSP的算法。此外，我们设计了精致的伯恩斯坦型信心集并提出了改进的算法，该算法可实现$ \ tilde {\ Mathcal {o}}}（d b _ {\ star} \ sqrt {k/c/c/c {k/c _ {\ min}}） $遗憾。为了补充遗憾的上限，我们还证明了$ \ omega（db _ {\ star} \ sqrt {k}）$的下限。因此，我们的改进算法将下限匹配到$ 1/\ sqrt {c _ {\ min}} $ factor和poly-logarithmic因素，从而实现了近乎最佳的遗憾保证。

Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to an INFORMS journal and should not be used to distribute the papers in print or online or to submit the papers to another publication.

我们研究汤普森采样对上下文匪徒的效率。现有的基于汤普森采样的算法需要构建后验分布的拉普拉斯近似（即高斯分布），这是在一般协方差矩阵中的高维应用中效率低下的效率。此外，高斯近似可能不是对一般奖励产生功能的后验分布的良好替代物。我们提出了一种有效的后采样算法，即Langevin Monte Carlo Thompson采样（LMC-TS），该采样（LMC-TS）使用Markov Chain Monte Carlo（MCMC）方法直接从上下文斑块中的后验分布中直接采样。我们的方法在计算上是有效的，因为它只需要执行嘈杂的梯度下降更新而不构建后验分布的拉普拉斯近似。我们证明，所提出的算法实现了相同的sublinear遗憾，作为一种特殊情况的汤普森采样算法，是上下文匪徒的特殊情况，即线性上下文的强盗。我们在不同上下文匪徒模型上对合成数据和现实世界数据集进行实验，这表明直接从后验进行采样既具有计算上有效又具有竞争性能。

我们建议使用$ \ tilde {o}（\ sqrt {\ kappa^{ - 1} \ phi t} \ phi t}）$ hears $ t $ the $ \ phi $ phi $是$ \ phi $是最olutimut，$ \ phi $是$ \ phi $，我们提出了一种用于广义线性奖励的新颖的上下文强盗算法。上下文协方差和$ \ kappa $的特征值是奖励差异的下限。在几种实际情况下，$ \ phi = o（d）$，我们的结果是带有$ \ sqrt {d} $的广义线性模型（GLM）土匪的第一个遗憾，而无需依赖Auer [2002]的方法。我们使用一个称为双重运动估计器的新型估计器（Doubly-bobust（DR）估计器的子类，但误差较紧，我们就实现了这种结合。 Auer [2002]的方法通过丢弃观察到的奖励来实现独立性，而我们的算法则在使用我们的DDR估计器的所有情况下实现了独立性。我们还提供了一个$ o（\ kappa^{ - 1} \ phi \ log（nt）\ log t）$遗憾在概率的边缘条件下以$ n $武器约束。 Bastani和Bayati [2020]和Bastani等人给出了遗憾的界限。 [2021]在环境中，所有臂都是共同的，但系数是特定的。当所有臂的上下文都不同，但系数很常见时，我们的第一个遗憾是在线性模型或GLM的边缘条件下绑定的。我们使用合成数据和真实示例进行实证研究，证明了我们的算法的有效性。

我们为随机最短路径（SSP）问题引入了两个新的无悔算法，其线性MDP显着改善了唯一的现有结果（Vial等，2021）。我们的第一算法是计算上的效率，实现了遗憾的绑定$ \ wideetilde {o} \ left（\ sqrt {d ^ 3b _ {\ star} ^ 2t _ {\ star} k}右）$，其中$ d $是维度特征空间，$ B _ {\ star} $和$ t _ {\ star} $分别是预期成本的上限，分别击中最佳政策的时间，$ k $是剧集的数量。具有略微修改的相同算法也实现了对数为OR o \ lex的对数后悔（\ frac {d ^ 3b _ {\ star} ^ 4} {c _ {\ min} ^ 2 \ text {gap} _ {\ min}} \ ln ^ 5 \ frac {db _ {\ star}} {c _ {\ min}} \右）$，其中$ \ text {gap} _ {\ min} $是最小的子项目差距和$ c_ { \ min} $是所有国家动作对的最低成本。我们的结果是通过开发更简单和改进的分析（Cohen等人，2021）的有限范围的分析而具有较小的近似误差，这可能具有独立兴趣。另一方面，在全局优化问题中使用方差感知的信心集，我们的第二算法是计算效率低下的，但实现了第一个“免费”后悔绑定$ \ widetilde {o}（d ^ {3.5} b _ {\ star } \ sqrt {k}）$与$ t _ {\ star} $或$ 1 / c _ {\ min} $，几乎匹配$ \ omega（db _ {\ star} \ sqrt {k}）$较低（Min等，2021）的绑定。

我们为随机线性匪徒问题提出了一种新的基于自举的在线算法。关键的想法是采用残留的自举勘探，在该探索中，代理商通过重新采样平均奖励估算的残差来估算下一步奖励。我们的算法，随机线性匪徒（\ texttt {linreboot}）的残留bootstrap探索，从其重新采样分布中估算了线性奖励，并以最高的奖励估计拉动了手臂。特别是，我们为理论框架做出了一个理论框架，以使基于自举的探索机制在随机线性匪徒问题中脱颖而出。关键见解是，Bootstrap探索的强度基于在线学习模型和残差的重新采样分布之间的乐观情绪。这样的观察使我们能够证明所提出的\ texttt {linreboot}确保了高概率$ \ tilde {o}（d \ sqrt {n}）$ sub-linear在温和条件下的遗憾。我们的实验支持\ texttt {重新启动}原理在线性匪徒问题的各种公式中的简易概括性，并显示了\ texttt {linreboot}的显着计算效率。