本文研究了固定置信度设置中随机多臂匪徒中最佳的手臂识别（BAI）问题。考虑到指数匪徒的一般类。指数匪徒家族的最先进算法面临计算挑战。为了缓解这些挑战，提出了一个新颖的框架，该框架将BAI问题视为顺序假设测试，并且可以适合针对指数的土匪家族的可拖动分析。基于此框架，设计了BAI算法，以利用规范顺序概率比测试。该算法在两种设置中都具有三个功能：（1）其样本复杂性在渐近上是最佳的，（2）保证它是$ \ delta- $ pac，（3）它解决了最先进的计算挑战 - 艺术方法。具体而言，这些方法仅专注于高斯环境，需要从汤普森（Thompson）的手臂上进行采样，而这些方法被认为是最好的和挑战者的手臂。本文分析表明，识别挑战者在计算上是昂贵的，并且提出的算法对其进行了规定。最后，提供了数值实验来支持分析。

出现了前两种算法，作为汤普森采样对多臂匪徒模型中最佳手臂识别的适应（Russo，2016），用于武器的参数家族。他们通过在两个候选臂，一个领导者和一个挑战者中随机化来选择下一个要采样的臂。尽管具有良好的经验表现，但仅当手臂是具有已知差异的高斯时，才能获得固定信心最佳手臂识别的理论保证。在本文中，我们提供了对两种方法的一般分析，该方法确定了领导者，挑战者和武器（可能是非参数）分布的理想特性。结果，我们获得了理论上支持的前两种算法，用于具有有限分布的最佳臂识别。我们的证明方法特别证明了用于选择从汤普森采样继承的领导者的采样步骤可以用其他选择代替，例如选择经验最佳的臂。

我们在随机匪徒上使用时（协变量）信息时，我们研究了固定信道的最佳武器识别问题。虽然我们可以在每轮中使用上下文信息，但我们对在语境分布上的边缘化平均奖励感兴趣。我们的目标是在给定值的错误率下识别最少数量的采样。我们显示出问题的特定实例的示例复杂性下限。然后，我们提出了一个“跟踪和停止”策略的上下文知识版本，其中ARM的比例绘制追踪一组最佳分配，并证明预期的ARM绘制数与渐近的下限匹配。我们证明，与Garivier＆Kaufmann（2016）的结果相比，可以使用上下文信息来提高最佳边缘化平均奖励的效率。我们通过实验证实了上下文信息有助于更快的最佳武器识别。

本文调查$ \纺织品{污染} $随机多臂爆炸中最佳臂识别问题。在此设置中，从任何臂获得的奖励由来自概率$ \ varepsilon $的对抗性模型的样本所取代。考虑了固定的置信度（无限地平线）设置，其中学习者的目标是识别最大的平均值。由于奖励的对抗污染，每个ARM的平均值仅部分可识别。本文提出了两种算法，基于连续消除的基于间隙的算法和一个，以便在亚高斯匪徒中最佳臂识别。这些算法涉及平均估计，从渐近估计的估计值达到真实均值的偏差上实现最佳误差保证。此外，这些算法渐近地实现了最佳的样本复杂性。具体地，对于基于差距的算法，样本复杂性呈渐近最佳到恒定因子，而对于基于连续的基于算法，​​它是最佳的对数因子。最后，提供了数值实验以说明与现有基线相比的算法的增益。

We investigate the sample complexity of learning the optimal arm for multi-task bandit problems. Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor). The objective is to learn the optimal (representation, predictor)-pair for each task, under the assumption that the optimal representation is common to all tasks. Within this framework, efficient learning algorithms should transfer knowledge across tasks. We consider the best-arm identification problem for a fixed confidence, where, in each round, the learner actively selects both a task, and an arm, and observes the corresponding reward. We derive instance-specific sample complexity lower bounds satisfied by any $(\delta_G,\delta_H)$-PAC algorithm (such an algorithm identifies the best representation with probability at least $1-\delta_G$, and the best predictor for a task with probability at least $1-\delta_H$). We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as $H(G\log(1/\delta_G)+ X\log(1/\delta_H))$, with $X,G,H$ being, respectively, the number of tasks, representations and predictors. By comparison, this scaling is significantly better than the classical best-arm identification algorithm that scales as $HGX\log(1/\delta)$.

考虑$ k $过程，每个过程都会生成一系列相同和独立的随机变量。这些过程的概率度量具有必须估计的随机参数。具体而言，它们共享一个参数$ \ theta $，所有概率度量共同。此外，每个过程$ i \ in \ {1，\ dots，k \} $都有一个私有参数$ \ alpha_i $。目的是设计一种主动采样算法，以顺序估算这些参数，以形成所有样品数量最少的共享和私有参数的可靠估计。该采样算法具有三个关键组件：（i）〜数据驱动的采样决策，随着时间的推移，该决策逐渐指定应选择哪些$ k $过程进行采样； （ii）〜停止该过程的时间，该过程指定何时累积数据足以形成可靠的估计并终止采样过程； （iii）〜所有共享和私人参数的估计器。由于已知的顺序估计在分析上是棘手的，因此本文采用\ emph {条件}估计成本函数，从而导致了顺序估计方法，该方法最近被证明可以进行拖延分析。划定了渐近的最佳决策规则（采样，停止和估计），并提供了数值实验，以将所提出的程序的疗效和质量与相关方法进行比较。

本文提出了新的偏差不等式，其在多武装强盗模型中的自适应采样下均匀地均匀。使用给定的一维指数家庭中的kullback-leibler发散来测量偏差，并且可以一次考虑几个臂。它们是通过基于分层的每个臂鞅构造而构建的，并通过将那些鞅乘以来获得。我们的偏差不平等允许我们根据广义概率比来分析一大类连续识别问题的概要概率比，并且为臂的装置的某些功能构造紧密的置信区间。

我们在随机多臂匪徒问题中使用固定预算和上下文（协变）信息研究最佳武器识别。在观察上下文信息之后，在每一轮中，我们使用过去的观察和当前上下文选择一个治疗臂。我们的目标是确定最好的治疗组，这是一个在上下文分布中被边缘化的最大预期奖励的治疗组，而错误识别的可能性最小。首先，我们为此问题得出半参数的下限，在这里我们将最佳和次优的治疗臂的预期奖励之间的差距视为感兴趣的参数，以及所有其他参数，例如在上下文中的预期奖励，作为滋扰参数。然后，我们开发“上下文RS-AIPW策略”，该策略由随机采样（RS）规则组成，跟踪目标分配比和使用增强反向概率加权（AIPW）估算器的建议规则。我们提出的上下文RS-AIPW策略是最佳的，因为错误识别概率的上限与预算到Infinity时的半参数下限相匹配，并且差距趋于零。

在纯探索问题中，依次收集信息以回答关于随机环境的问题。虽然近年来对线性匪徒的最佳武器识别进行了广泛的研究，但很少有作品专门用于识别一只手臂，即$ \ varepsilon $ close close close to to to to to to n of the $ \ varepsilon $ close（也不是最好的一只）。在这个有几个正确答案的问题中，识别算法应重点放在这些答案之间的一个候选人上，并验证其正确。我们证明，以最高平均值选择答案不允许算法就预期的样本复杂性达到渐近最优性。相反，应识别\ textit {最远的答案}。使用该洞察力仔细选择候选人答案，我们开发了一个简单的过程，以适应最佳臂识别算法，以应对托管线性随机匪徒中的$ \ varepsilon $ best-best-andwer识别。最后，我们为此设置提出了一种渐近最佳算法，该算法证明可以针对现有的改良最佳臂识别算法实现竞争性的经验性能。

我们考虑使用未知差异的双臂高斯匪徒的固定预算最佳臂识别问题。当差异未知时，性能保证与下限的性能保证匹配的算法最紧密的下限和算法的算法很长。当算法不可知到ARM的最佳比例算法。在本文中，我们提出了一种策略，该策略包括在估计的ARM绘制的目标分配概率之后具有随机采样（RS）的采样规则，并且使用增强的反概率加权（AIPW）估计器通常用于因果推断文学。我们将我们的战略称为RS-AIPW战略。在理论分析中，我们首先推导出鞅的大偏差原理，当第二次孵化的均值时，可以使用，并将其应用于我们提出的策略。然后，我们表明，拟议的策略在错误识别的可能性达到了Kaufmann等人的意义上是渐近最佳的。 （2016）当样品尺寸无限大而双臂之间的间隙变为零。

主动学习可以减少执行假设测试所需的样本数量并估计模型的参数。在本文中，我们重新审视Chernoff的作品，所述工作描述了用于执行假设测试的渐近最佳算法。我们获得了对Chernoff的算法的新颖性复杂性，具有非渐近术语，其在固定置信水平处具有其性能。我们还开发了Chernoff采样的延伸，可用于估计各种模型的参数，并且我们在估计误差上获得非渐近绑定。我们将延长Chernoff采样延伸，积极学习神经网络模型，并估算实际数据线性和非线性回归问题中的参数，其中我们的方法有利地对最先进的方法执行。

积极的学习方法在减少学习所需的样本数量方面表现出了巨大的希望。随着自动化学习系统被采用到实时的现实世界决策管道中，越来越重要的是，这种算法的设计考虑到了安全性。在这项工作中，我们研究了在互动环境中学习最佳安全决定的复杂性。我们将这个问题减少到约束的线性匪徒问题，我们的目标是找到满足某些（未知）安全限制的最佳手臂。我们提出了一种基于自适应的实验性设计算法，在显示ARM的难度与次优的难度之间，我们表现出了有效的交易。据我们所知，我们的结果是具有安全限制的线性匪徒最佳武器识别。实际上，我们证明了这种方法在合成和现实世界数据集上的表现很好。

我们研究汤普森采样（TS）算法的遗憾，指数为家庭土匪，其中奖励分配来自一个一维指数式家庭，该家庭涵盖了许多常见的奖励分布，包括伯努利，高斯，伽玛，伽玛，指数等。我们建议汤普森采样算法，称为expts，它使用新颖的采样分布来避免估计最佳臂。我们为expts提供了严格的遗憾分析，同时产生有限的遗憾和渐近遗憾。特别是，对于带指数级家庭奖励的$ k $臂匪徒，expts of horizo​​n $ t $ sub-ucb（对于有限的时间遗憾的是问题依赖的有限时间标准） $ \ sqrt {\ log k} $，并且对于指数家庭奖励，渐近最佳。此外，我们通过在Expts中使用的采样分配外添加一个贪婪的剥削步骤，提出$^+$，以避免过度估计亚最佳武器。 expts $^+$是随时随地的强盗算法，可用于指数级的家庭奖励分布同时实现最小值和渐近最优性。我们的证明技术在概念上很简单，可以轻松地应用于用特定奖励分布分析标准的汤普森抽样。

我们考虑固定预算的最佳手臂识别问题，目标是找到具有固定数量样本的最大均值的手臂。众所周知，错误识别最好的手臂的概率对巡回赛的数量成倍小。但是，已经讨论了有关此值的速率（指数）的有限特征。在本文中，我们表征了由于所有可能的参数的全局优化而导致的最佳速率。我们介绍了两个费率，$ r^{\ mathrm {go}} $和$ r^{\ mathrm {go}} _ {\ infty} $，对应于错误识别概率的下限，每种范围都与A建议的算法。费率$ r^{\ mathrm {go}} $与$ r^{\ mathrm {go}} $ - 跟踪相关联，可以通过神经网络有效地实现，并显示出胜过现有的算法。但是，此速率要求可以实现非平凡的条件。为了解决这个问题，我们介绍了第二个速率$ r^{\ mathrm {go}} _ \ infty $。我们表明，通过引入一种称为延迟最佳跟踪（DOT）的概念算法，确实可以实现此速率。

我们认为“政策选择”问题 - 否则称为强盗文献中的最佳臂识别 - 由Kasy和Sautmann（2021）提出的适应性实验设计。Kasy和Sautmann（2021）的定理提供了三种渐近结果，为该环境开发的探索采样提供了理论担保。首先表明定理1（1）的证明具有技术问题，定理1（2）的证明和声明是不正确的。然后，我们通过一个反例来展示定理1（3）是假的。对于前两者，我们纠正了陈述并提供严格的证据。对于定理1（3），我们提出了一种替代目标函数，我们称之为后加权政策遗憾，并导出勘探采样的渐近最优性。

控制蜂窝网络中的天线倾斜必须在网络覆盖和容量之间达到有效的权衡。在本文中，我们设计了从现有数据（在所谓的被动学习设置中）的算法最佳倾斜控制策略或由算法主动生成的数据（活动学习设置）。我们将这种算法的设计形式形式线性多臂杆（CL-MAb）中的最佳策略识别（BPI）问题。一个手臂代表天线倾斜更新;上下文捕获当前的网络条件;奖励对应于改善性能，混合覆盖和容量;目标是识别，具有给定的置信度，一个大约最佳的政策（将上下文映射到具有最大奖励的手臂的函数。对于CL-MAB在主动和被动学习设置中，我们在任何算法返回近似最佳策略所需的样本数量上获得信息 - 理论下限，以及实现这些基本限制的设计算法。我们将我们的算法应用于蜂窝网络中的远程电气倾斜（RET）优化问题，并显示它们可以使用比天真或现有的规则的学习算法更少的数据采样产生最佳倾斜更新策略。

我们探索了一个新的强盗实验模型，其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆，而那些执行正确的推理面部信息延迟的算法。我们的主要见解是，我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率，但是在硬性非平稳性方面显示出令人惊讶的弹性，这会导致其他自适应算法失败。

级别设置估计问题旨在查找域$ {\ 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中的函数近似于未知的拼写，并为此设置中隐含和显式案件提供新的算法，具有很强的理论保证。此外，在线性（内核）设置中，我们表明我们的界限几乎是最佳的，即，我们的上限与阈值线性匪徒的现有下限匹配。据我们所知，这项工作提供了第一个实例依赖性非渐近的上限，就匹配信息理论下限的水平设定估计的样本复杂性。

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

我们在固定的误差率$ \ delta $（固定信道TOP-M识别）下最大的手段识别M武器的问题，用于错过的线性匪盗模型。这个问题是由实际应用的动机，特别是在医学和推荐系统中，由于它们的简单性和有效算法的存在，线性模型很受欢迎，但是数据不可避免地偏离线性。在这项工作中，我们首先在普通Top-M识别问题的任何$ \ delta $ -correct算法的样本复杂性上得出了一个易行的下限。我们表明，知道从线性度偏差的偏差是利用问题的结构所必需的。然后，我们描述了该设置的第一个算法，这既实际，也适应了误操作。我们从其样本复杂度推出了一个上限，证实了这种适应性，与$ \ delta $ $ \ lightarrow $ 0匹配。最后，我们在合成和现实世界数据上评估了我们的算法，表现出尊重的竞争性能到现有的基准。