移动边缘计算有助于用户将计算任务卸载到边缘服务器，以满足其严格的延迟要求。以前的作品主要探讨给出系统侧信息时的任务卸载（例如，服务器处理速度，蜂窝数据速率）或系统不确定性的集中卸载。但两者普遍跌倒，以处理涉及动态和不确定环境中许多共存用户的任务安置。在本文中，我们开发了考虑未知随机系统侧信息的多用户卸载框架，以实现分散的用户发起的服务放置。具体而言，我们将动态任务放置作为在线多用户多武装强盗过程，并提出基于分散的epoch的卸载（DEBO），以优化在网络延迟下进行的用户奖励。我们表明DEBO可以推断最佳用户服务器分配，从而实现了近距离的服务性能和紧密的O（log t）卸载后悔。此外，我们将DEBO概括为各种常见场景，如未知的奖励差距，动态进入或离开客户，以及公平的奖励分发，同时进一步探索用户卸载任务需要异构计算资源。特别是，我们为这些实例中的每一个完成子线性遗憾。基于实际测量的评估证实了我们在优化延迟敏感奖励的最先进方法中的卸载方案的优势。

我们考虑一个完全分散的多人多手随机多武装匪盗匪徒，其中玩家不能互相通信，并且只能观察自己的行为和奖励。环境可能与不同的播放器不同，$ \ texit {i.e.} $，给定臂的奖励分布在球员之间是异构的。在碰撞的情况下（当多个玩家播放相同的手臂时），我们允许碰撞玩家接收非零奖励。播放武器的时间 - 地平线$ t $是\ emph {否}对玩家已知。在此设置中，允许玩家的数量大于武器的数量，我们展示了一项达到订单优化预期令人遗憾的政策$ O（\ log ^ {1 + delta} t）$有些$ 0 <\ delta <1 $超过时间的时间$ t $。IEEE关于信息理论的交易中接受了本文。

Multi-player multi-armed bandit is an increasingly relevant decision-making problem, motivated by applications to cognitive radio systems. Most research for this problem focuses exclusively on the settings that players have \textit{full access} to all arms and receive no reward when pulling the same arm. Hence all players solve the same bandit problem with the goal of maximizing their cumulative reward. However, these settings neglect several important factors in many real-world applications, where players have \textit{limited access} to \textit{a dynamic local subset of arms} (i.e., an arm could sometimes be ``walking'' and not accessible to the player). To this end, this paper proposes a \textit{multi-player multi-armed walking bandits} model, aiming to address aforementioned modeling issues. The goal now is to maximize the reward, however, players can only pull arms from the local subset and only collect a full reward if no other players pull the same arm. We adopt Upper Confidence Bound (UCB) to deal with the exploration-exploitation tradeoff and employ distributed optimization techniques to properly handle collisions. By carefully integrating these two techniques, we propose a decentralized algorithm with near-optimal guarantee on the regret, and can be easily implemented to obtain competitive empirical performance.

在本文中，我们研究了一个多级多服务器排队系统，其具有代表作业和服务器的特征向量的Bilinear模型之后的作业服务器分配随机奖励。我们的目标是对oracle策略的遗憾最小化，该策略具有完整的系统参数信息。我们提出了一种调度算法，该算法使用线性强盗算法以及动态作业分配给服务器。对于基线设置，其中均值工作时间与所有作业相同，我们表明我们的算法具有子线性遗憾，以及在地平线时间内的平均队列长度上的子线性绑定。我们进一步示出了类似的界限在更一般的假设下保持，允许不同的作业类别的非相同均值工作时间和一组时变的服务器类。我们还表明，可以通过访问作业类的交通强度的算法来保证更好的遗憾和均值队列长度界限。我们呈现数值实验的结果，示出了我们算法的遗憾和平均队列长度依赖于各种系统参数，并将它们的性能与先前提出的算法进行比较，使用合成随机生成的数据和真实世界集群计算数据跟踪。

我们通过可共享的手臂设置概括了多武器的多臂土匪（MP-MAB）问题，其中几场比赛可以共享同一臂。此外，每个可共享的组都有有限的奖励能力和“每载”奖励分配，这两者都是学习者所不知道的。可共享臂的奖励取决于负载，这是“每载”奖励乘以拉动手臂的戏剧数量或当比赛数量超过容量限制时的奖励能力。当“按负载”奖励遵循高斯分布时，我们证明了样本复杂性的下限，从负载依赖的奖励中学习容量，也遗憾的是这个新的MP-MAB问题的下限。我们设计了一个容量估计器，其样品复杂性上限在奖励手段和能力方面与下限匹配。我们还提出了一种在线学习算法来解决该问题并证明其遗憾的上限。这个遗憾的上界的第一任期与遗憾的下限相同，其第二和第三个术语显然也对应于下边界。广泛的实验验证了我们算法的性能以及其在5G和4G基站选择中的增长。

我们考虑随机多武装强盗（MAB）问题，延迟影响了行动。在我们的环境中，过去采取的行动在随后的未来影响了ARM奖励。在现实世界中，行动的这种延迟影响是普遍的。例如，为某个社会群体中的人员偿还贷款的能力可能历史上历史上批准贷款申请的频率频率。如果银行将贷款申请拒绝拒绝弱势群体，则可以创建反馈循环，进一步损害该群体中获取贷款的机会。在本文中，我们制定了在多武装匪徒的背景下的行动延迟和长期影响。由于在学习期间，我们将强盗设置概括为对这种“偏置”的依赖性进行编码。目标是随着时间的推移最大化收集的公用事业，同时考虑到历史行动延迟影响所产生的动态。我们提出了一种算法，实现了$ \ tilde {\ mathcal {o}}的遗憾，并显示$ \ omega（kt ^ {2/3}）$的匹配遗憾下限，其中$ k $是武器数量，$ t $是学习地平线。我们的结果通过添加技术来补充强盗文献，以处理具有长期影响的行动，并对设计公平算法有影响。

通信瓶颈和数据隐私是联邦多武装强盗（MAB）问题中的两个至关重要的问题，例如通过无线连接车辆的决策和建议的情况。在本文中，我们在这些问题中设计了隐私保留的通信有效的算法，并在遗憾方面研究隐私，沟通和学习绩效之间的互动。具体而言，我们设计隐私保留的学习算法和通信协议，并在网络私人代理在主工作人员，分散和混合结构中进行在线强盗学习时，从而导出学习遗憾。我们的强盗学习算法基于每个代理和代理在每个时代结束时与服务器/彼此交换学习知识的庞大的子最优手臂。此外，我们采用差异隐私（DP）方法在交换信息时保护每个代理人的数据隐私;并且我们通过减少频繁的沟通与较少的代理商参与来缩短沟通成本。通过分析我们拟议的算法框架，在硕士劳动，分散和混合结构中的暗示框架，理论上显示了遗憾和沟通成本/隐私之间的权衡。最后，我们经验展示了与我们理论分析一致的这些权衡。

在包括在线广告，合同招聘和无线调度的各种应用中，控制器受到可用资源的严格预算约束的限制，这些资源由每个动作以随机量消耗，以及可能施加的随机可行性约束关于决策的重要运作限制。在这项工作中，我们考虑一个常规模型来解决这些问题，每个行动都返回一个随机奖励，成本和罚款从未知的联合分配返回，决策者旨在最大限度地提高预算约束下的总奖励$ B $在总成本和随机限制的时间平均罚款。我们提出了一种基于Lyapunov优化方法的新型低复杂性算法，命名为$ {\ tt lyon} $，并证明它以$ k $武器实现$ o（\ sqrt {kb \ log b}）$后悔和零约束 - 当$ B $足够大时。 $ {\ tt lyon} $的计算成本和尖锐性能界限表明，基于Lyapunov的算法设计方法可以有效地解决受约束的强盗优化问题。

通过新兴应用程序，如现场媒体电子商务，促销和建议，我们介绍和解决了一般的非静止多武装强盗问题，具有以下两个特征：（i）决策者可以拉动和收集每次期间，从最多$ k \，（\ ge 1）美元的奖励; （ii）手臂拉动后的预期奖励立即下降，然后随着ARM空闲时间的增加，非参数恢复。目的是最大化预期累计奖励超过$ T $时间段，我们设计了一类“纯粹的周期性政策”，共同设置了拉动每个臂的时间。对于拟议的政策，我们证明了离线问题和在线问题的性能保证。对于脱机问题，当已知所有型号参数时，所提出的周期性策略获得1- \ Mathcal O（1 / \ Sqrt {k}）$的近似率，当$ k $生长时是渐近的最佳状态到无穷远。对于在线问题时，当模型参数未知并且需要动态学习时，我们将脱机周期性策略与在线策略上的上部置信程序进行集成。拟议的在线策略被证明是对脱机基准的近似拥有$ \ widetilde {\ mathcal o}（n \ sqrt {t}）。我们的框架和政策设计可能在更广泛的离线规划和在线学习应用程序中阐明，具有非静止和恢复奖励。

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.

动态治疗方案（DTRS）是个性化的，适应性的，多阶段的治疗计划，可将治疗决策适应个人的初始特征，并在随后的每个阶段中的中级结果和特征，在前阶段受到决策的影响。例子包括对糖尿病，癌症和抑郁症等慢性病的个性化一线和二线治疗，这些治疗适应患者对一线治疗，疾病进展和个人特征的反应。尽管现有文献主要集中于估算离线数据（例如从依次随机试验）中的最佳DTR，但我们研究了以在线方式开发最佳DTR的问题，在线与每个人的互动都会影响我们的累积奖励和我们的数据收集，以供我们的数据收集。未来的学习。我们将其称为DTR匪徒问题。我们提出了一种新颖的算法，通过仔细平衡探索和剥削，可以保证当过渡和奖励模型是线性时，可以实现最佳的遗憾。我们证明了我们的算法及其在合成实验和使用现实世界中对重大抑郁症的适应性治疗的案例研究中的好处。

由于信息不对称，多智能经纪增强学习（Marl）问题是挑战。为了克服这一挑战，现有方法通常需要代理商之间的高度协调或沟通。我们考虑具有在应用中产生的分层信息结构的两个代理多武装匪徒（MAB）和MARKOV决策过程（MDP），我们利用不需要协调或通信的更简单和更高效的算法。在结构中，在每个步骤中，“领导者”首先选择她的行动，然后“追随者”在观察领导者的行动后，“追随者”决定他的行动。这两个代理观察了相同的奖励（以及MDP设置中的相同状态转换），这取决于其联合行动。对于强盗设置，我们提出了一种分层匪盗算法，实现了$ \ widetilde {\ mathcal {o}}（\ sqrt {abt}）$和近最佳差距依赖的近乎最佳的差距遗憾$ \ mathcal {o}（\ log（t））$，其中$ a $和$ b $分别是领导者和追随者的行动数，$ t $是步数。我们进一步延伸到多个追随者的情况，并且具有深层层次结构的情况，在那里我们都获得了近乎最佳的遗憾范围。对于MDP设置，我们获得$ \ widetilde {\ mathcal {o}}（\ sqrt {h ^ 7s ^ 2abt}）$后悔，其中$ h $是每集的步骤数，$ s $是数量各国，$ T $是剧集的数量。这与$ a，b $和$ t $的现有下限匹配。

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.

与传统机器学习（ML）相比，联邦学习（FL）被认为是解决移动设备的数据隐私问题的吸引力框架。使用Edge Server（ESS）作为中间人在接近度执行模型聚合可以减少传输开销，并且它能够在低延迟FL中实现很大的潜力，其中FL（HFL）的分层体系结构被吸引更多地关注。设计适当的客户选择策略可以显着提高培训性能，并且已广泛用于FL研究。然而，据我们所知，没有专注于HFL的研究。此外，HFL的客户选择面临的挑战比传统的FL更多，例如，客户端 - es对的时变连接和网络运营商的有限预算（否）。在本文中，我们调查了HFL的客户选择问题，其中no no学习成功参与客户的数量以改善培训性能（即，在每轮中选择多个客户端）以及每个ES的有限预算。基于上下文组合多武装强盗（CC-MAB）开发了一个称为上下文知识的在线客户选择（COCS）的在线策略。 COCs观察局部计算和客户端对传输的侧信息（上下文），并使客户选择决策最大化没有给出有限预算的实用程序。理论上，与强凸和非凸HFL上的Oracle策略相比，COCS遗憾地实现了载体遗憾。仿真结果还支持拟议的COCS政策对现实世界数据集的效率。

We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number ($k$) of choices has better reward (or loss) before making its choice. In this model, we derive algorithms whose regret bounds have exponentially better dependence on the time horizon compared to the classic regret bounds. In particular, we show that probing with $k=2$ suffices to achieve time-independent regret bounds for online linear and convex optimization. The same number of probes improve the regret bound of stochastic MAB with independent arms from $O(\sqrt{nT})$ to $O(n^2 \log T)$, where $n$ is the number of arms and $T$ is the horizon length. For stochastic MAB, we also consider a stronger model where a probe reveals the reward values of the probed arms, and show that in this case, $k=3$ probes suffice to achieve parameter-independent constant regret, $O(n^2)$. Such regret bounds cannot be achieved even with full feedback after the play, showcasing the power of limited ``advice'' via probing before making the play. We also present extensions to the setting where the hints can be imperfect, and to the case of stochastic MAB where the rewards of the arms can be correlated.

多ARM强盗（MAB）是一种经典的在线学习框架，可以研究在不确定的环境中的顺序决策。然而，MAB框架忽略了决策者不能直接采取行动（例如，拉臂）的情况。在许多应用中，这是一种实际重要的场景，例如频谱共享，众脉和边缘计算。在这些申请中，决策者将激励其他自私的代理商进行预期的行动（即，在决策者代表武器上撤销）。本文在此方案中建立了激励的在线学习（IOL）框架。设计IOL框架的关键挑战是未知环境学习和非对称信息启示的紧密耦合。为了解决这个问题，我们基于该特殊的拉格朗日功能，我们提出了一种对IOL框架的社会最优机制。我们的机制满足各种理想的属性，如代理公平，激励兼容性和自愿参与。它达到了与需要额外信息的最先进的基准相同的渐近性能。我们的分析还推出了IOL框架中人群的力量：更大的代理人群使我们的机制能够更接近社会绩效的理论上限。数值结果表明了我们在大型边缘计算中的机制的优点。

The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the stochastic multi-armed bandit problem. More precisely, for the stochastic two-armed bandit problem, the expected regret in time T is O( ln T ∆ + 1 ∆ 3 ). And, for the stochastic N -armed bandit problem, the expected regret in time) 2 ln T ). Our bounds are optimal but for the dependence on ∆i and the constant factors in big-Oh.

在线学习通常需要探索以最大程度地提高长期奖励，但这是以短期“遗憾”为代价的。我们研究如何在多个小组之间分担这种探索成本。例如，在临床试验环境中，分配了亚最佳治疗的患者有效地产生了勘探成本。当患者根据种族或年龄与自然群体相关联时，自然要问任何单一群体所承担的探索成本是否“公平”。如此有动力，我们介绍了“分组”的强盗模型。我们利用公理讨价还价的理论，尤其是纳什议价解决方案，以形式化可能构成跨群体勘探成本的公平分裂的方式。一方面，我们表明，任何遗憾的政策都引起了最不公平的结果：此类政策将在可能的情况下传递最“处于弱势”的群体。更具建设性的方式，我们得出了最佳公平且同时享受“公平价格”的政策。我们通过对华法林剂量的上下文匪徒进行案例研究来说明我们的算法框架的相对优点，我们关注多个种族和年龄段的探索成本。

我们研究了\ textit {在线}低率矩阵完成的问题，并使用$ \ mathsf {m} $用户，$ \ mathsf {n} $项目和$ \ mathsf {t} $ rounds。在每回合中，我们建议每个用户一项。对于每个建议，我们都会从低级别的用户项目奖励矩阵中获得（嘈杂的）奖励。目的是设计一种以下遗憾的在线方法（以$ \ mathsf {t} $）。虽然该问题可以映射到标准的多臂强盗问题，其中每个项目都是\ textit {独立}手臂，但由于没有利用武器和用户之间的相关性，因此遗憾会导致遗憾。相比之下，由于低级别的歧管的非凸度，利用奖励矩阵的低排列结构是具有挑战性的。我们使用探索-Commit（etc）方法克服了这一挑战，该方法确保了$ O（\ Mathsf {polylog}（\ Mathsf {m}+\ \ \ \ \ Mathsf {n}）\ Mathsf {t}^{2/2/ 3}）$。 That is, roughly only $\mathsf{polylog} (\mathsf{M}+\mathsf{N})$ item recommendations are required per user to get non-trivial solution.我们进一步改善了排名$ 1 $设置的结果。在这里，我们提出了一种新颖的算法八进制（使用迭代用户群集的在线协作过滤），以确保$ O（\ Mathsf {polylog}（\ Mathsf {M}+\ Mathsf {N}）几乎最佳的遗憾。 ^{1/2}）$。我们的算法使用了一种新颖的技术，可以共同和迭代地消除项目，这使我们能够在$ \ Mathsf {t} $中获得几乎最小的最佳速率。

汤普森抽样（TS）吸引了对强盗区域的兴趣。它在20世纪30年代介绍，但近年来尚未经过理论上证明。其在组合多武装强盗（CMAB）设置中的所有分析都需要精确的Oracle来提供任何输入的最佳解决方案。然而，这种Oracle通常是不可行的，因为许多组合优化问题是NP - 硬，并且只有近似oracles可用。一个例子（王和陈，2018）已经表明TS的失败来学习近似Oracle。但是，此Oracle罕见，仅用于特定问题实例。它仍然是一个开放的问题，无论TS的收敛分析是否可以扩展到CMAB中的精确oracle。在本文中，我们在贪婪的Oracle下研究了这个问题，这是一个常见的（近似）Oracle，具有理论上的保证来解决许多（离线）组合优化问题。我们提供了一个问题依赖性遗憾的遗憾下限为$ \ omega（\ log t / delta ^ 2）$，以量化Ts的硬度来解决贪婪的甲骨文的CMAB问题，其中$ T $是时间范围和$ Delta $是一些奖励差距。我们还提供几乎匹配的遗憾上限。这些是TS解决CMAB与常见近似甲骨文的第一个理论结果，并打破TS无法使用近似神谕的误解。