我们研究了在线多任务学习的问题，其中在相似但不一定相同的多臂强盗环境中执行任务。特别是，我们研究学习者如何通过知识转移来改善多个相关任务的整体绩效。虽然最近已证明，在所有任务同时解决的环境中，尚不清楚汤普森采样（TS）算法是否尚不清楚，虽然最近证明了基于上限的算法（UCB）算法几乎达到了最佳的性能保证，具有类似的理论属性。在这项工作中，我们为更通用的在线多任务学习协议提供了TS-Type算法，该协议扩展了并发设置。我们提供了其频繁的分析，并证明它在随机停止时间内使用新型浓度不平等的多任务数据聚集也几乎是最佳的。最后，我们评估了关于合成数据的算法，并表明与基于UCB的算法相比，TS-Type算法具有出色的经验性能和基线算法，该算法在没有转移的情况下为每个单独的任务执行TS。

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.

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

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the stateof-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied version of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of Õ(d 3/2 √ T ) (or Õ(d T log(N ))), which is the best regret bound achieved by any computationally efficient algorithm for this problem, and is within a factor of √ d (or log(N )) of the information-theoretic lower bound for this problem.

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

我们在非稳定性或时间变化偏好下，在$ k $的武器{动态遗憾最小化}中研究了\ mpph {动态遗憾最小化}。这是一个在线学习设置，其中代理在每个轮中选择一对项目，并仅观察该对的相对二进制`的次数“反馈，从该圆的底层偏好矩阵中采样。我们首先研究对抗性偏好序列的静态后悔最小化问题，并使用$ O（\ SQRT {kt}）为高概率遗憾设计了高效的算法。我们接下来使用类似的算法思想，提出一种在非实践中的两种概念下的动态遗为最小化的高效且可透明的最佳算法。特别是，我们建立$ \ to（\ sqrt {skt}）$和$ \ to（{v_t ^ {1/3} k ^ {1/3} t ^ {2/3}}）$动态后悔保证，$ S $是基础偏好关系中的“有效交换机”的总数，以及$ V_T $的衡量标准的“连续变化”非公平性。尽管现实世界系统中的非静止环境实用性，但在这项工作之前尚未研究这些问题的复杂性。我们通过证明在上述非实践概念下的符合下限保证匹配的匹配的算法来证明我们的算法的最优性。最后，我们通过广泛的模拟来证实我们的结果，并比较我们算法在最先进的基线上的功效。

在本文中，我们研究了汤普森采样（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，m] $范围内支持的有限分布相关。我们不认为$ [m，m] $是已知的范围，并表明学习此范围有成本。确实，出现了与分销相关和无分配后悔界限之间的新权衡，这阻止了同时实现典型的$ \ ln t $和$ \ sqrt {t} $ bunds。例如，仅当与分布相关的遗憾界限至少属于$ \ sqrt {t} $的顺序时，才能实现$ \ sqrt {t} $}无分布遗憾。我们展示了一项策略，以实现新的权衡表明的遗憾。

我们研究了批量线性上下文匪徒的最佳批量遗憾权衡。对于任何批次数$ M $，操作次数$ k $，时间范围$ t $和维度$ d $，我们提供了一种算法，并证明了其遗憾的保证，这是由于技术原因，具有两阶段表达作为时间的时间$ t $ grose。我们还证明了一个令人奇迹的定理，令人惊讶地显示了在问题参数的“问题参数”中的两相遗憾（最高〜对数因子）的最优性，因此建立了确切的批量后悔权衡。与最近的工作\ citep {ruan2020linear}相比，这表明$ m = o（\ log \ log t）$批次实现无需批处理限制的渐近最佳遗憾的渐近最佳遗憾，我们的算法更简单，更易于实际实现。此外，我们的算法实现了所有$ t \ geq d $的最佳遗憾，而\ citep {ruan2020linear}要求$ t $大于$ d $的不切实际的大多项式。沿着我们的分析，我们还证明了一种新的矩阵集中不平等，依赖于他们的动态上限，这是我们的知识，这是其文学中的第一个和独立兴趣。

在本文中，我们研究了时间速度与非IID数据的协作学习模型中学习过程的交流次数之间的权衡，其中多个代理与可能不同的环境互动，他们希望学习一个目标。汇总环境。我们在匪徒理论中使用一个基本问题，称为多臂匪徒中最佳ARM识别作为传递以下概念信息的工具：对非IID数据的协作学习比在IID数据上更加困难。特别是，我们显示以下内容：a）非IID数据设置中的加速度可能小于$ 1 $（即放缓）。当回合$ r = o（1）$的数量时，我们将至少需要多项式数量的代理（就武器数量而言）来实现大于$ 1 $的加速。这与IID数据设置形成鲜明对比，在$ r \ ge 2 $中，无论代理数量如何，加速度总是至少$ 1 $。 b）学习过程中的适应性无济于事。这与IID数据设置形成鲜明对比，为了实现相同的速度，最佳的非自适应算法需要比最佳自适应算法要大得多。在技​​术空间中，我们进一步开发了Arxiv：1904.03293中引入的广义消除技术。我们表明，在使用复杂的硬输入分布并直接证明自适应算法的下限时，分配类别的隐式表示非常有用。

本文统一了设计，简化了风险厌恶汤普森采样算法的分析，为多武装爆炸问题的常规风险功能为$ \ rho $。在大偏差理论中使用收缩原理，我们证明了这些连续风险功能的新型浓度界限。与现有的作品相比，所界限取决于样本本身，我们的范围仅取决于样本的数量。这使我们能够以追求的分析挑战，并统一现有汤普森采样的算法的遗憾范围。我们展示了广泛的风险功能以及它们的“漂亮”功能满足连续性条件。使用我们新开发的分析工具包，我们分析了算法$ \ rho $ -mts（对于多项式发行版）和$ \ rho $ -npts（对于有界分布），并证明他们承认渐近最佳的风险厌恶算法的最佳遗憾平均方差，CVAR等普遍存在风险措施，以及一系列新综合的风险措施。数值模拟表明，我们的界限是相当严格的VIS-\“A-VIS算法无关的下限。

我们在嵌套政策类别的存在下研究匪徒场景中的模型选择问题，目的是获得同时的对抗和随机性（“两全其美”）高概率的遗憾保证。我们的方法要求每个基础学习者都有一个候选人的遗憾约束，可能会或可能不会举行，而我们的元算法按照一定时间表来扮演每个基础学习者，该时间表使基础学习者的候选人后悔的界限保持平衡，直到被发现违反他们的保证为止。我们开发了专门设计的仔细的错误指定测试，以将上述模型选择标准与利用环境的（潜在良性）性质的能力相结合。我们在对抗环境中恢复畜栏算法的模型选择保证，但是在实现高概率后悔界限的附加益处，特别是在嵌套对抗性线性斑块的情况下。更重要的是，我们的模型选择结果也同时在差距假设​​下的随机环境中同时保持。这些是在（线性）匪徒场景中执行模型选择时，可以达到世界上最好的（随机和对抗性）保证的第一个理论结果。

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

在本文中，我们考虑了在规避风险的标准下线性收益的上下文多臂强盗问题。在每个回合中，每个手臂都会揭示上下文，决策者选择一只手臂拉动并获得相应的奖励。特别是，我们将均值变化视为风险标准，最好的组是具有最大均值奖励的均值。我们将汤普森采样算法应用于脱节模型，并为提出算法的变体提供全面的遗憾分析。对于$ t $ rounds，$ k $ Actions和$ d $ - 维功能向量，我们证明了$ o（（1+ \ rho+\ frac {1} {1} {\ rho}）{\ rho}）d \ ln t \ ln t \ ln的遗憾。 \ frac {k} {\ delta} \ sqrt {d k t^{1+2 \ epsilon} \ ln \ frac {k} {\ delta} \ frac {1} {\ epsilon}} $ 1 - \ \ delta $在带有风险公差$ \ rho $的均值方差标准下，对于任何$ 0 <\ epsilon <\ frac {1} {2} $，$ 0 <\ delta <1 $。我们提出的算法的经验性能通过投资组合选择问题来证明。

我们考虑具有未知实用程序参数的多项式logit模型（MNL）下的动态分类优化问题。本文研究的主要问题是$ \ varepsilon $ - 污染模型下的模型错误指定，该模型是强大统计和机器学习中的基本模型。特别是，在整个长度$ t $的销售范围内，我们假设客户根据$（1- \ varepsilon）$ - 时间段的$（1- \ varepsilon）的基础多项式logit选择模型进行购买，并进行任意购买取而代之的是在剩余的$ \ varepsilon $ - 分数中的决策。在此模型中，我们通过主动淘汰策略制定了新的强大在线分类优化政策。我们对遗憾建立上限和下界，并表明当分类能力恒定时，我们的政策是$ t $的最佳对数因素。分类能力具有恒定的上限。我们进一步制定了一种完全自适应策略，该政策不需要任何先验知识，即污染参数$ \ varepsilon $。如果存在最佳和亚最佳产品之间存在的亚临时差距，我们还建立了依赖差距的对数遗憾上限和已知的 - $ \ VAREPSILON $和UNKNOWER-$ \ \ VAREPSILON $案例。我们的仿真研究表明，我们的政策表现优于基于上置信度范围（UCB）和汤普森采样的现有政策。

在古典语境匪徒问题中，在每轮$ t $，学习者观察一些上下文$ c $，选择一些动作$ i $执行，并收到一些奖励$ r_ {i，t}（c）$。我们考虑此问题的变体除了接收奖励$ r_ {i，t}（c）$之外，学习者还要学习其他一些上下文$的$ r_ {i，t}（c'）$的值C'$ in设置$ \ mathcal {o} _i（c）$;即，通过在不同的上下文下执行该行动来实现的奖励\ mathcal {o} _i（c）$。这种变体出现在若干战略设置中，例如学习如何在非真实的重复拍卖中出价，最热衷于随着许多平台转换为运行的第一价格拍卖。我们将此问题称为交叉学习的上下文匪徒问题。古典上下围匪徒问题的最佳算法达到$ \ tilde {o}（\ sqrt {ckt}）$遗憾针对所有固定策略，其中$ c $是上下文的数量，$ k $的行动数量和$ $次数。我们设计并分析了交叉学习的上下文匪徒问题的新算法，并表明他们的遗憾更好地依赖上下文的数量。在选择动作时学习所有上下文的奖励的完整交叉学习下，即设置$ \ mathcal {o} _i（c）$包含所有上下文，我们显示我们的算法实现后悔$ \ tilde {o}（ \ sqrt {kt}）$，删除$ c $的依赖。对于任何其他情况，即在部分交叉学习下，$ | \ mathcal {o} _i（c）| <c $ for $（i，c）$，遗憾界限取决于如何设置$ \ mathcal o_i（c）$影响上下文之间的交叉学习的程度。我们从Ad Exchange运行一流拍卖的广告交换中模拟了我们的真实拍卖数据的算法，并表明了它们优于传统的上下文强盗算法。

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

我们考虑$ 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 $武装的随机土匪提供基于索引的策略的经典后悔界限的证明。

Maillard（2013）的博士论文呈现了$ k $武装匪徒问题的随机算法。我们呼叫Maillard采样（MS）的这种缺少已知的算法计算以封闭形式选择每个臂的概率，这对于从强盗数据的反事实评估有用，而是缺乏来自汤普森采样，这是一种广泛采用的匪徒行业算法。通过这种优点，我们重新审视MS并进行改进的分析，以表明它实现了渐近最优性和$ \ SQRT {kt \ log {k}} $ minimax后悔绑定在$ t $是时间界限，它与之匹配标准渐近最佳的UCB的性能。然后，我们提出了一个称为MS $ ^ + $的MS的变体，这将改善其最小绑定到$ \ sqrt {kt \ log {k}} $，而不会失去渐近最优值。 $ ^ + $ MS也可以调整为攻击性（即，较少的探索），而不会失去理论担保，从现有强盗算法无法使用的独特功能。我们的数值评估显示了MS $ ^ + $的有效性。

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