我们以已知的奖励和未知的约束来研究顺序决策，这是由约束代表昂贵评估人类偏好（例如安全舒适的驾驶行为）的情况所激发的。我们将互动学习这些约束作为新的线性匪徒问题的挑战正式化，我们称之为约束的线性最佳臂识别。为了解决这个问题，我们提出了自适应约束学习（ACOL）算法。我们为约束线性最佳臂识别提供了一个依赖实例的下限，并表明Acol的样品复杂性与最坏情况下的下限匹配。在平均情况下，ACOL的样品复杂性结合仍然比简单方法的边界更紧密。在合成实验中，ACOL与Oracle溶液相同，并且表现优于一系列基准。作为应用程序，我们考虑学习限制，以代表驾驶模拟中的人类偏好。对于此应用，ACOL比替代方案要高得多。此外，我们发现学习偏好作为约束对驾驶场景的变化比直接编码奖励函数中的偏好更强大。

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

逆增强学习（IRL）是从专家演示中推断奖励功能的强大范式。许多IRL算法都需要已知的过渡模型，有时甚至是已知的专家政策，或者至少需要访问生成模型。但是，对于许多现实世界应用，这些假设太强了，在这些应用程序中，只能通过顺序相互作用访问环境。我们提出了一种新颖的IRL算法：逆增强学习（ACEIRL）的积极探索，该探索积极探索未知的环境和专家政策，以快速学习专家的奖励功能并确定良好的政策。 Aceirl使用以前的观察来构建置信区间，以捕获合理的奖励功能，并找到关注环境最有用区域的勘探政策。 Aceirl是使用样品复杂性界限的第一种活动IRL的方法，不需要环境的生成模型。在最坏情况下，Aceirl与活性IRL的样品复杂性与生成模型匹配。此外，我们建立了一个与问题相关的结合，该结合将Aceirl的样品复杂性与给定IRL问题的次级隔离间隙联系起来。我们在模拟中对Aceirl进行了经验评估，发现它的表现明显优于更幼稚的探索策略。

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

对于许多强化学习（RL）应用程序，指定奖励是困难的。本文考虑了一个RL设置，其中代理仅通过查询可以询问可以的专家来获取有关奖励的信息，例如，评估单个状态或通过轨迹提供二进制偏好。从如此昂贵的反馈中，我们的目标是学习奖励的模型，允许标准RL算法实现高预期的回报，尽可能少的专家查询。为此，我们提出了信息定向奖励学习（IDRL），它使用奖励的贝叶斯模型，然后选择要最大化信息增益的查询，这些查询是有关合理的最佳策略之间的返回差异的差异。与针对特定类型查询设计的先前主动奖励学习方法相比，IDRL自然地适应不同的查询类型。此外，它通过将焦点转移降低奖励近似误差来实现类似或更好的性能，从而降低奖励近似误差，以改善奖励模型引起的策略。我们支持我们的调查结果，在多个环境中进行广泛的评估，并具有不同的查询类型。

我们考虑在可实现的环境中进行交互式学习，并开发一般框架，以处理从最佳ARM识别到主动分类的问题。我们开始调查，即观察到可怕算法\ emph {无法实现可实现的设置中最佳最佳状态。因此，我们设计了新的计算有效的算法，可实现最可实现的设置，该算法与对数因子的最小限制相匹配，并且是通用的，适用于包括内核方法的各种功能类，H {\“O}偏置函数，以及凸起功能。我们的算法的样本复杂性可以在众所周知的数量中量化，如延长的教学尺寸和干草堆维度。然而，与直接基于这些组合量的算法不同，我们的算法是计算效率的。实现计算效率，我们的算法使用Monte Carlo“命令运行”算法来从版本空间中的样本，而不是明确地维护版本空间。我们的方法有两个关键优势。首先，简单，由两个统一，贪婪的算法组成。第二，我们的算法具有能够无缝地利用经常可用和在实践中有用的知识。此外为了我们的新理论结果，我们经验证明我们的算法与高斯过程UCB方法具有竞争力。

多武装强盗环境中最好的武器识别问题是许多真实世界决策问题的一个优秀模式，但它无法捕捉到现实世界中，在学习时通常必须满足安全限制的事实。在这项工作中，我们研究了安全关键环境中最好的武器识别问题，代理的目标是找到许多人的最佳安全选项，同时以保证某些方式达到满足肯定的方式的探索，最初是未知的安全约束。我们首先在奖励和安全约束采用线性结构的情况下分析此问题，并显示近乎匹配的上限和下限。然后，我们分析了更多的常规版本，我们只假设奖励和安全约束可以通过单调函数建模，并在此设置中提出算法，保证安全地学习。我们的结论与实验结果表明我们在方案中的方法的有效性，如安全地识别许多人以便治疗疾病。

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

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

Performance of machine learning algorithms depends critically on identifying a good set of hyperparameters. While recent approaches use Bayesian optimization to adaptively select configurations, we focus on speeding up random search through adaptive resource allocation and early-stopping. We formulate hyperparameter optimization as a pure-exploration nonstochastic infinite-armed bandit problem where a predefined resource like iterations, data samples, or features is allocated to randomly sampled configurations. We introduce a novel algorithm, Hyperband, for this framework and analyze its theoretical properties, providing several desirable guarantees. Furthermore, we compare Hyperband with popular Bayesian optimization methods on a suite of hyperparameter optimization problems. We observe that Hyperband can provide over an order-of-magnitude speedup over our competitor set on a variety of deep-learning and kernel-based learning problems.

在线强化学习（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 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)$.

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

我们研究固定预算设置中线性匪徒中最佳手臂识别的问题。通过利用G-Optimal设计的属性并将其纳入ARM分配规则，我们设计了一种无参数算法，基于最佳设计的基于设计的线性最佳臂识别（OD-Linbai）。我们提供了OD-Linbai的失败概率的理论分析。 OD-Linbai的性能并非所有最优差距，而是取决于顶部$ d $臂的差距，其中$ d $是线性匪徒实例的有效维度。补充，我们为此问题提供了一个Minimax下限。上限和下限表明，OD-Linbai是最佳的最佳选择，直到指数中的恒定乘法因素，这是对现有方法的显着改进（例如，贝耶斯加普，和平，线性化和GSE），并解决了确定确定该问题的问题。在固定预算设置中学习最好的手臂的困难。最后，数值实验表明，对各种真实和合成数据集的现有算法进行了相当大的经验改进。

汤普森抽样（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无法使用近似神谕的误解。

在本文中，我们研究了汤普森采样（TS）方法的应用到随机组合多臂匪徒（CMAB）框架中。当所有基本臂的结果分布都是独立的，并获得$ o（m \ log k _ {\ max} \ log t / \ delta_时，我们首先分析一般CMAB模型的标准TS算法。 {\ min}）$，其中$ m $是基本武器的数量，$ k _ {\ max} $是最大的超级臂的大小，$ t $是时间范围，而$ \ delta _ {\ min} $是最佳解决方案的预期奖励与任何非最佳解决方案之间的最小差距。这种遗憾的上限比$ o（m（\ log k _ {\ max}）^2 \ log t / \ delta _ {\ min}）$更好。此外，我们的新颖分析技术可以帮助收紧其他基于UCB的政策（例如ESC）的遗憾界限，因为我们改善了计算累积遗憾的方法。然后，我们考虑Matroid Bandit设置（CMAB模型的特殊类别），在这里我们可以删除跨武器的独立性假设，并实现与下限匹配的遗憾上限。除了遗憾的上限外，我们还指出，一个人不能直接替换确切的离线甲骨文（将离线问题实例的参数作为输入，并在此实例下输出确切的最佳操作），用TS算法中的近似oracle替换了ts算法的近似值。甚至经典的mAb问题。最后，我们使用一些实验来显示TS遗憾与其他现有算法之间的比较，实验结果表明TS优于现有基准。

通过在线实验和违规学习中的实践需求激励，我们研究了安全最佳设计的问题，在那里我们开发了一个有效探索的数据记录策略，同时通过基线生产政策实现竞争奖励。我们首先展示，也许令人惊讶的是，尽管安全，但尽管安全，但尽管是安全的，但仍有统一探索的常见做法是最大化信息增益的次优。然后，我们提出了一个安全的最佳日志记录策略，因为没有有关操作的预期奖励的侧面信息。我们通过考虑侧面信息来改进这种设计，并且还通过线性奖励模型扩展到大量动作的方法。我们分析了我们的数据记录策略如何影响禁止策略学习中的错误。最后，我们通过进行广泛的实验，经验验证了我们设计的好处。

富达匪徒问题是$ k $的武器问题的变体，其中每个臂的奖励通过提供额外收益的富达奖励来增强，这取决于播放器如何对该臂进行“忠诚”在过去。我们提出了两种忠诚的模型。在忠诚点模型中，额外奖励的数量取决于手臂之前播放的次数。在订阅模型中，额外的奖励取决于手臂的连续绘制的当前数量。我们考虑随机和对抗问题。由于单臂策略在随机问题中并不总是最佳，因此对抗性环境中遗憾的概念需要仔细调整。我们介绍了三个可能的遗憾和调查，这可以是偏执的偏执。我们详细介绍了增加，减少和优惠券的特殊情况（玩家在手臂的每辆M $播放后获得额外的奖励）保真奖励。对于不一定享受载体遗憾的模型，我们提供了最糟糕的下限。对于那些展示Sublinear遗憾的模型，我们提供算法并绑定他们的遗憾。

这项工作考虑了最佳手臂识别的选择性采样问题。给定一组潜在选项$ \ mathcal {z} \ subset \ mathbb {r} ^ d $，学习者旨在计算概率大于1- \ delta $，$ \ arg \ max_ {z \ mathcal { z}} z ^ {\ top} \ theta _ {\ ast} $ where $ \ theta _ {\ art} $未知。在每个时间步骤中，潜在的测量$ x_t \ in \ mathcal {x} \ subset \ mathbb {r} ^ d $被绘制的iid，学习者可以选择采取测量，在这种情况下，他们观察到嘈杂的测量$ x ^ {\ top} \ theta _ {\ ast} $，或弃权采取测量并等待可能更多的信息点到达流。因此，学习者在他们采取的标签样本数量之间面临的基本折衷，并且当他们收集足够的证据来宣布最好的手臂并停止抽样时。这项工作的主要结果精确地表征了标记的样本和停止时间之间的这种权衡，并提供了一种算法，几乎最佳地实现了给出所需停止时间的最小标签复杂性。此外，我们表明最佳决策规则具有基于决定点是否处于椭圆形的简单几何形式。最后，我们的框架足以捕获先前作品的二进制分类。

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