我们考虑一个强盗问题，决策者可以在任何时候在她的考虑设置中添加新的武器。一个新的手臂以“手臂库”为代价，其中包含有限的“手臂类型”，每个手臂都以明显的平均奖励为特征。查询成本反映出返回的手臂是最佳选择的可能性，决策者不知道。此功能封装了定义一系列受操作启发的在线学习问题的特征，例如，在流失的市场中产生的特征，或涉及涉及昂贵资源收购的分配的特征。决策者的目标是最大程度地提高其累积的预期收益，这是一系列拉动的收益，忽略了统计属性以及查询武器的类型。我们研究了储层分布中的两种自然内生性模式，并表征了（紧密的）必要条件，以实现该问题的次线性遗憾。我们还提供了内生性对针对问题的静态版本（无内生性）量身定制算法的影响的粒状分析。在此过程中，我们提出了一种新的算法，并提供了精致的分析，从而为现有文献提供了更严格的范围。我们认为我们的发现可能会引起广泛的兴趣，并指导该地区未来的工作。

关于强盗算法最佳设计的许多文献都是基于最小化预期遗憾的基础。众所周知，在某些指数家庭中最佳的设计可以实现预期的遗憾，即以LAI-ROBBINS下降的速度在ARM游戏数量上进行对数增长。在本文中，我们表明，当人们使用这种优化的设计时，相关算法的遗憾分布必然具有非常沉重的尾巴，特别是cauchy分布的尾巴。此外，对于$ p> 1 $，遗憾分布的$ p $'瞬间增长速度要比多层型的速度快得多，尤其是作为ARM播放总数的力量。我们表明，优化的UCB强盗设计在另一种意义上也是脆弱的，即，当问题甚至略有指定时，遗憾的增长可能比传统理论所建议的要快得多。我们的论点是基于标准的量化想法，并表明最有可能的遗憾变得比预期的要大的方法是最佳手臂在前几只手臂比赛中返回低于平均水平的奖励，从而导致算法相信这一点手臂是最佳的。为了减轻暴露的脆弱性问题，我们表明可以修改UCB算法，以确保对错误指定的理想程度。在此过程中，我们还提供了UCB勘探数量与产生后悔分布的尾声之间的巨大权衡。

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

我们考虑了一种有可能无限的武器的随机强盗问题。我们为最佳武器和$ \ delta $的比例写入$ p ^ * $，以获得最佳和次优臂之间的最小含义 - 均值差距。我们在累积遗憾设置中表征了最佳学习率，以及在问题参数$ t $（预算），$ p ^ * $和$ \ delta $的最佳臂识别环境中。为了最大限度地减少累积遗憾，我们提供了订单$ \ OMEGA（\ log（t）/（p ^ * \ delta））$的下限和UCB样式算法，其匹配上限为一个因子$ \ log（1 / \ delta）$。我们的算法需要$ p ^ * $来校准其参数，我们证明了这种知识是必要的，因为在这个设置中调整到$ p ^ * $以来，因此是不可能的。为了获得最佳武器识别，我们还提供了订单$ \ Omega（\ exp（-ct \ delta ^ 2 p ^））的较低限制，以上输出次优臂的概率，其中$ c> 0 $是一个绝对常数。我们还提供了一个消除算法，其上限匹配下限到指数中的订单$ \ log（t）$倍数，并且不需要$ p ^ * $或$ \ delta $ as参数。我们的结果直接适用于竞争$ j $ -th最佳手臂的三个相关问题，识别$ \ epsilon $良好的手臂，并找到一个平均值大于已知订单的大分的手臂。

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

我们考虑$ k $武装的随机土匪，并考虑到$ t $ t $的累积后悔界限。我们对同时获得最佳订单$ \ sqrt {kt} $的策略感兴趣，并与发行依赖的遗憾相关，即与$ \ kappa \ ln t $相匹配，该遗憾是最佳的。和Robbins（1985）以及Burnetas和Katehakis（1996），其中$ \ kappa $是最佳问题依赖性常数。这个常数的$ \ kappa $取决于所考虑的模型$ \ Mathcal {d} $（武器上可能的分布家族）。 M \'Enard and Garivier（2017）提供了在一维指数式家庭给出的模型的参数案例中实现这种双重偏见的策略，而Lattimore（2016，2018）为（Sub）高斯分布的家族而做到了这一点。差异小于$ 1 $。我们将此结果扩展到超过$ [0,1] $的所有分布的非参数案例。我们通过结合Audibert和Bubeck（2009）的MOSS策略来做到这一点，该策略享受了最佳订单$ \ sqrt {kt} $的无分配遗憾，以及Capp \'e等人的KL-UCB策略。 （2013年），我们为此提供了对最佳分布$ \ kappa \ ln t $遗憾的首次分析。我们能够在努力简化证明（以前已知的遗憾界限，因此进行的新分析）时，能够获得这种非参数两次审查结果；因此，本贡献的第二个优点是为基于$ k $武装的随机土匪提供基于索引的策略的经典后悔界限的证明。

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

本文介绍了信息性多臂强盗（IMAB）模型，在每个回合中，玩家选择手臂，观察符号，并以符号的自我信息形式获得未观察到的奖励。因此，手臂的预期奖励是产生其符号的源质量函数的香农熵。玩家的目标是最大程度地提高与武器的熵值相关的预期奖励。在假设字母大小是已知的假设下，为IMAB模型提出了两种基于UCB的算法，该算法考虑了插件熵估计器的偏差。第一种算法在熵估计中乐观地纠正了偏置项。第二算法依赖于数据依赖性置信区间，该置信区间适应具有较小熵值的源。性能保证是通过上限为每种算法的预期遗憾提供的。此外，在Bernoulli案例中，将这些算法的渐近行为与伪遗憾的Lai-Robbins的下限进行了比较。此外，在假设\ textit {cract}字母大小的假设下是未知的，而播放器仅知道其上方的宽度上限，提出了一种基于UCB的算法，在其中，玩家的目的是减少由该算法造成的遗憾。未知的字母尺寸在有限的时间方面。数字结果说明了论文中介绍的算法的预期遗憾。

我们考虑腐烂奖励的无限多臂匪徒问题，其中手臂的平均奖励是根据任意趋势在每次拉动的手臂上减小的，最大腐烂速率$ \ varrho = o（1）$。我们表明，这个学习问题具有$ \ omega（\ max \ {\ varrho^{1/3} t，\ sqrt {t} \}）$ worst-case遗憾的遗憾下降下降，其中$ t $是$ t $。我们表明，匹配的上限$ \ tilde {o}（\ max \ {\ varrho^{1/3} t，\ sqrt {t} \}）$，最多可以通过多元素来实现当算法知道最大腐烂速率$ \ varrho $时，一种使用UCB索引的算法，该算法使用UCB索引和一个阈值来决定是否继续拉动手臂或从进一步考虑中移除手臂。我们还表明，$ \ tilde {o}（\ max \ {\ varrho^{1/3} t，t^{3/4} \}）$遗憾的上限可以通过不知道的算法来实现$ \ varrho $的值通过使用自适应UCB索引以及自适应阈值值。

我们研究了生存的匪徒问题，这是Perotto等人在开放问题中引入的多臂匪徒问题的变体。（2019年），对累积奖励有限制；在每个时间步骤中，代理都会获得（可能为负）奖励，如果累积奖励变得低于预先指定的阈值，则该过程停止，并且这种现象称为废墟。这是研究可能发生毁灭但并非总是如此的框架的第一篇论文。我们首先讨论，在对遗憾的天真定义下，统一的遗憾是无法实现的。接下来，我们就废墟的可能性（以及匹配的策略）提供紧密的下限。基于此下限，我们将生存后悔定义为最小化和提供统一生存后悔的政策的目标（至少在整体奖励的情况下），当时Time Horizon $ t $是已知的。

我们考虑激励探索：一种多臂匪徒的版本，其中武器的选择由自私者控制，而算法只能发布建议。该算法控制信息流，信息不对称可以激励代理探索。先前的工作达到了最佳的遗憾率，直到乘法因素，这些因素根据贝叶斯先验而变得很大，并在武器数量上成倍规模扩展。采样每只手臂的一个更基本的问题一旦遇到了类似的因素。我们专注于激励措施的价格：出于激励兼容的目的，绩效的损失，广泛解释为。我们证明，如果用足够多的数据点初始化，则标准的匪徒汤普森采样是激励兼容的。因此，当收集这些数据点时，由于激励措施的绩效损失仅限于初始回合。这个问题主要降低到样本复杂性的问题：需要多少个回合？我们解决了这个问题，提供了匹配的上限和下限，并在各种推论中实例化。通常，最佳样品复杂性在“信念强度”中的武器数量和指数中是多项式。

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

在线学习和决策中的一个核心问题 - 从土匪到强化学习 - 是要了解哪种建模假设会导致样本有效的学习保证。我们考虑了一个普遍的对抗性决策框架，该框架涵盖了（结构化的）匪徒问题，这些问题与对抗性动力学有关。我们的主要结果是通过新的上限和下限显示决策估计系数，这是Foster等人引入的复杂度度量。在与我们环境的随机对应物中，对于对抗性决策而言是必要和足够的遗憾。但是，与随机设置相比，必须将决策估计系数应用于所考虑的模型类（或假设）的凸壳。这就确定了容纳对抗奖励或动态的价格受凸层化模型类的行为的约束，并恢复了许多现有结果 - 既积极又负面。在获得这些保证的途径中，我们提供了新的结构结果，将决策估计系数与其他众所周知的复杂性度量的变体联系起来，包括Russo和Van Roy的信息比以及Lattimore和Gy的探索目标\“ {o} rgy。

我们考虑在一般函数近似下，考虑了经典增强学习（RL）环境的模型选择 - 多武装强盗（mAb）和马尔可夫决策过程（MDPS）。在模型选择框架中，我们不知道函数类，由$ \ MATHCAL {F} $和$ \ MATHCAL {M} $表示，其中True Models-奖励MABS的奖励生成函数以及MDPS的过渡内核 - - 分别撒谎。取而代之的是，我们获得了$ M $嵌套功能（假设）类，使得真正的模型包含在至上的类别中。在本文中，我们提出并分析了MAB和MDP的有效模型选择算法，将\ Emph {Adapt} \ emph {Adapt}到最小的函数类（在嵌套的$ M $类中），其中包含真实的基础模型。在嵌套假设类别的可分离性假设下，我们表明我们的自适应算法的累积后悔与知道正确功能类（即$ \ cf $和$ \ cm $）的Oracle的累积后悔相匹配。此外，对于这两种设置，我们都表明，模型选择的成本是一个遗憾的术语，因为它对学习范围$ t $的弱（对数）依赖性弱（对数）。

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

We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega(\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.

我们设计了简单，最佳的政策，以确保在经典的多武器匪徒问题中确保对重尾风险的安全。最近，\ cite {fan2021偏差}表明，信息理论优化的匪徒算法患有严重的重尾风险；也就是说，最糟糕的案例可能会以$ 1/t $的速度慢慢衰减，其中$ t $是时间范围。受其结果的启发，我们进一步表明，广泛使用的政策，例如标准的上限约束政策和汤普森采样政策也会产生重型风险。实际上，对于所有“依赖实例依赖的一致”政策，这种重型风险实际上存在。为了确保对这种重型风险的安全性，对于两臂强盗设置，我们提供了一种简单的政策设计，即（i）具有最差的最佳性能，可用于预期的遗憾$ \ tilde o（\ sqrt {t} ）$和（ii）具有最坏的尾巴概率，即以指数率$ \ exp（ - \ omega（\ sqrt {t}））$产生线性遗憾衰减。我们进一步证明，尾巴概率的这种指数衰减率在所有具有最差最佳最优性的政策中都是最佳的，这些损失率是预期的。最后，我们使用任意$ k $的武器数量将政策设计和分析改进了一般环境。我们为在政策设计下的任何遗憾阈值中提供详细的尾巴概率表征。也就是说，产生大于$ x $的遗憾的最坏情况是由$ \ exp（ - \ omega（x/\ sqrt {kt}））$上限。进行数值实验以说明理论发现。我们的结果揭示了对一致性和轻尾风险之间不兼容的见解，而这表明对预期的遗憾和轻尾风险的最佳最佳性是兼容的。

当他们更喜欢$ \ texit {exploit} $时，您如何激励自我兴趣的代理到$ \ texit {探索} $？我们考虑复杂的探索问题，其中每个代理面临相同（但未知）MDP。与传统的加固学习配方相比，代理商控制了政策的选择，而算法只能发出建议。然而，该算法控制信息流，并且可以通过信息不对称激励代理探索。我们设计一种算法，探讨MDP中的所有可达状态。我们达到了类似于先前研究的静态，无国籍探索问题中激励探索的保证担保。据我们所知，这是第一个考虑在有状态，强化学习环境中设计的工作。

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.

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