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

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

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

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

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

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

许多工业和安全应用程序采用套件传感器，用于检测时间行为模式的突然变化。这些突然的变化通常在本地显现，只渲染一个小型传感器信息。由于资源约束，每个传感器的连续监视可能是昂贵的，并且作为强盗最快转换点检测问题的动机，其中顺序地选择感测动作（或传感器），并且仅观察到对应于所选动作的测量。我们在有限的有限参数化概率分布的一般类别的检测延迟上获得了一个信息 - 理论下限。然后，我们提出了一种计算上有效的在线传感方案，这无缝地平衡了对不同传感选项的需求，利用查询信息行动。我们推导出拟议方案的预期延误界限，并表明这些界限在低误报率下以低误报率下限，建立了所提出的方法的最优性。然后，我们对合成和实时数据集进行了许多实验，证明了我们提出的方法的有效性。

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

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

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

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

我们为依次随机实验提出了一种新的扩散 - 反应分析，包括在解决多臂匪徒问题中出现的扩散分析。在使用$ n $时间步骤的实验中，我们让动作规模之间的平均奖励差距到$ 1/\ sqrt {n} $，以将学习任务的难度保留为$ n $的增长。在这个方案中，我们表明，一类顺序随机的马尔可夫实验的行为收敛到扩散极限，作为对随机微分方程的解决方案。因此，扩散极限使我们能够得出顺序实验的随机动力学的精致实例特异性表征。我们使用扩散极限来获得一些关于顺序实验的遗憾和信念演变的新见解，包括汤普森采样。一方面，我们表明，当奖励差距相对较大时，所有随机概率的顺序实验都具有lipchitz连续的依赖性。另一方面，我们发现，汤普森（Thompson）的样本具有渐近性的先验差异，达到了近乎特定实例的遗憾缩放，包括较大的奖励差距。但是，尽管使用非信息先验对汤普森采样产生了良好的遗憾，但我们表明，随着时间的流逝，诱发的后验信仰非常不稳定。

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

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.

在线强化学习（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 - 我们获得改进或新颖的样本复杂性保证。

在强盗多个假设测试中，每个ARM对应于我们希望测试的不同NULL假设，并且目标是设计正确识别大型有趣的武器（真正发现）的自适应算法，同时仅错误地识别少数不感兴趣的武器（虚假的发现）。非强盗多测试中的一个常见度量是错误的发现速率（FDR）。我们为强盗FDR控制提出了一个统一的模块化框架，强调了探索和证据总结的解耦。我们利用了强大的鞅的“e-processage”概念，以确保在通用问题设置中进行任意复合空无效，探索规则和停止时间的FDR控制。特别地，即使臂的奖励分布可能是相关的，有效的FDR控制也可以依赖，可以同时查询多个臂，并且多个（协作或竞争）代理可以是查询臂，也可以是覆盖组合半强盗类型设置。在每次步骤中，每次ARM奖励分配是独立的，并且在每个步骤都会审议了每个ARM奖励分配的环境。我们的框架在这​​个特殊情况下恢复了匹配的样本复杂性保证，在实践中表现相对或更好。对于其他设置，示例复杂性将取决于问题的更精细的细节（正在测试的复合空，探索算法，数据依赖结构，停止规则），我们不会探索这些;我们的贡献是表明FDR保证对这些细节进行了干净，完全不可知。

Sequential testing, always-valid $p$-values, and confidence sequences promise flexible statistical inference and on-the-fly decision making. However, unlike fixed-$n$ inference based on asymptotic normality, existing sequential tests either make parametric assumptions and end up under-covering/over-rejecting when these fail or use non-parametric but conservative concentration inequalities and end up over-covering/under-rejecting. To circumvent these issues, we sidestep exact at-least-$\alpha$ coverage and focus on asymptotically exact coverage and asymptotic optimality. That is, we seek sequential tests whose probability of ever rejecting a true hypothesis asymptotically approaches $\alpha$ and whose expected time to reject a false hypothesis approaches a lower bound on all tests with asymptotic coverage at least $\alpha$, both under an appropriate asymptotic regime. We permit observations to be both non-parametric and dependent and focus on testing whether the observations form a martingale difference sequence. We propose the universal sequential probability ratio test (uSPRT), a slight modification to the normal-mixture sequential probability ratio test, where we add a burn-in period and adjust thresholds accordingly. We show that even in this very general setting, the uSPRT is asymptotically optimal under mild generic conditions. We apply the results to stabilized estimating equations to test means, treatment effects, etc. Our results also provide corresponding guarantees for the implied confidence sequences. Numerical simulations verify our guarantees and the benefits of the uSPRT over alternatives.

我们考虑一个预期值排名和选择问题，其中所有K解决方案的仿真输出都取决于常见的不确定输入模型。鉴于输入模型的不确定性是由有限支持的概率单纯捕获的，我们将最佳最佳（MPB）定义为最佳概率最大的解决方案。为了设计有效的采样算法以找到MPB，我们首先得出了一个错误选择MPB的概率的较大偏差率，然后提出最佳计算预算分配（OCBA）问题，以找到最佳的静态采样比率的最佳静态采样率所有解决方案输入模型对最大化下限。我们设计了一系列顺序算法，这些算法应用于可解释和计算有效的采样规则，并证明其采样比达到了随着仿真预算的增加而达到OCBA问题的最佳条件。该算法针对用于上下文排名和选择问题的最新顺序抽样算法进行了基准测试，并证明在查找MPB时具有出色的经验性能。

在因果推理和强盗文献中，基于观察数据的线性功能估算线性功能的问题是规范的。我们分析了首先估计治疗效果函数的广泛的两阶段程序，然后使用该数量来估计线性功能。我们证明了此类过程的均方误差上的非反应性上限：这些边界表明，为了获得非反应性最佳程序，应在特定加权$ l^2 $中最大程度地估算治疗效果的误差。 -规范。我们根据该加权规范的约束回归分析了两阶段的程序，并通过匹配非轴突局部局部最小值下限，在有限样品中建立了实例依赖性最优性。这些结果表明，除了取决于渐近效率方差之外，最佳的非质子风险除了取决于样本量支持的最富有函数类别的真实结果函数与其近似类别之间的加权规范距离。

我们研究了随机近似程序，以便基于观察来自ergodic Markov链的长度$ n $的轨迹来求近求解$ d -dimension的线性固定点方程。我们首先表现出$ t _ {\ mathrm {mix}} \ tfrac {n}} \ tfrac {n}} \ tfrac {d}} \ tfrac {d} {n} $的非渐近性界限。$ t _ {\ mathrm {mix $是混合时间。然后，我们证明了一种在适当平均迭代序列上的非渐近实例依赖性，具有匹配局部渐近最小的限制的领先术语，包括对参数$的敏锐依赖（d，t _ {\ mathrm {mix}}） $以高阶术语。我们将这些上限与非渐近Minimax的下限补充，该下限是建立平均SA估计器的实例 - 最优性。我们通过Markov噪声的政策评估导出了这些结果的推导 - 覆盖了所有$ \ lambda \中的TD（$ \ lambda $）算法，以便[0,1）$ - 和线性自回归模型。我们的实例依赖性表征为HyperParameter调整的细粒度模型选择程序的设计开放了门（例如，在运行TD（$ \ Lambda $）算法时选择$ \ lambda $的值）。