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

我们考虑了一种有可能无限的武器的随机强盗问题。我们为最佳武器和$ \ 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 $良好的手臂，并找到一个平均值大于已知订单的大分的手臂。

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

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

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

我们介绍了一个多臂强盗模型，其中奖励是多个随机变量的总和，每个动作只会改变其中的分布。每次动作之后，代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的，在该系统中，变量代表单个客户的结果，例如点击。我们提出了UCB风格的算法，以估计基线上的动作的提升。我们研究了问题的多种变体，包括何时未知基线和受影响的变量，并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限，以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。

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

在古典语境匪徒问题中，在每轮$ 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运行一流拍卖的广告交换中模拟了我们的真实拍卖数据的算法，并表明了它们优于传统的上下文强盗算法。

在臂分布的标准假设下广泛研究了随机多臂强盗问题（例如，用已知的支持，指数家庭等）。这些假设适用于许多现实世界问题，但有时他们需要知识（例如，在尾部上），从业者可能无法精确访问，提高强盗算法的鲁棒性的问题，以模拟拼盘。在本文中，我们研究了一种通用的Dirichlet采样（DS）算法，基于通过重新采样的武器观测和数​​据相关的探索奖励计算的经验指标的成对比较。我们表明，当该策略的界限和对数后悔具有轻度分量度条件的半界分布时，这种策略的不同变体达到了可证明的最佳遗憾。我们还表明，一项简单的调整在大类无界分布方面实现了坚固性，其成本比对数渐近的遗憾略差。我们终于提供了数字实验，展示了合成农业数据的决策问题中DS的优点。

我们研究了多人多武装匪徒的信息共享与合作问题。我们提出了第一个算法，实现了这个问题的对数遗憾。我们的结果基于两项创新。首先，我们表明对连续消除策略的简单修改可用于允许玩家在没有碰撞的情况下估计它们的子项货间隙，直到恒定因素。其次，我们利用第一个结果来设计一种成功使用碰撞的小额奖励来协调玩家之间的通信协议，同时保留有意义的实例依赖性对数后悔保证。

我们通过审查反馈重复进行一定的第一价格拍卖来研究在线学习，在每次拍卖结束时，出价者只观察获胜的出价，学会了适应性地出价，以最大程度地提高她的累积回报。为了实现这一目标，投标人面临着一个具有挑战性的困境：如果她赢得了竞标 - 获得正收益的唯一方法 - 然后她无法观察其他竞标者的最高竞标，我们认为我们认为这是从中汲取的。一个未知的分布。尽管这一困境让人联想到上下文强盗中的探索探索折衷权，但现有的UCB或汤普森采样算法无法直接解决。在本文中，通过利用第一价格拍卖的结构属性，我们开发了第一个实现$ o（\ sqrt {t} \ log^{2.5} t）$ hearry bund的第一个学习算法（\ sqrt {t} \ log^{2.5} t），这是最小值的最低$ $ \ log $因素，当投标人的私人价值随机生成时。我们这样做是通过在一系列问题上提供算法，称为部分有序的上下文匪徒，该算法将图形反馈跨动作，跨环境跨上下文进行结合，以及在上下文中的部分顺序。我们通过表现出一个奇怪的分离来确定该框架的优势和劣势，即在随机环境下几乎可以独立于动作/背景规模的遗憾，但是在对抗性环境下是不可能的。尽管这一通用框架有限制，但我们进一步利用了第一价格拍卖的结构，并开发了一种学习算法，该算法在存在对手生成的私有价值的情况下，在存在的情况下可以有效地运行样本（并有效地计算）。我们建立了一个$ o（\ sqrt {t} \ log^3 t）$遗憾，以此为此算法，因此提供了对第一价格拍卖的最佳学习保证的完整表征。

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

本文在动态定价的背景下调查预先存在的离线数据对在线学习的影响。我们在$ t $期间的销售地平线上研究单一产品动态定价问题。每个时段的需求由产品价格根据具有未知参数的线性需求模型确定。我们假设在销售地平线开始之前，卖方已经有一些预先存在的离线数据。离线数据集包含$ N $示例，其中每个标准是由历史价格和相关的需求观察组成的输入输出对。卖方希望利用预先存在的离线数据和顺序在线数据来最大限度地减少在线学习过程的遗憾。我们的特征在于在线学习过程的最佳遗憾的脱机数据的大小，位置和分散的联合效果。具体而言，离线数据的大小，位置和色散由历史样本数量为$ n $，平均历史价格与最佳价格$ \ delta $之间的距离以及历史价格的标准差价Sigma $分别。我们表明最佳遗憾是$ \ widetilde \ theta \ left（\ sqrt {t} \ wedge \ frac {t} {（n \ wedge t）\ delta ^ 2 + n \ sigma ^ 2} \右）$，基于“面对不确定性”原则的“乐观主义”的学习算法，其遗憾是最佳的对数因子。我们的结果揭示了对脱机数据的大小的最佳遗憾率的惊人变换，我们称之为阶段转型。此外，我们的结果表明，离线数据的位置和分散也对最佳遗憾具有内在效果，我们通过逆平面法量化了这种效果。

We study the best-arm identification problem in multi-armed bandits with stochastic, potentially private rewards, when the goal is to identify the arm with the highest quantile at a fixed, prescribed level. First, we propose a (non-private) successive elimination algorithm for strictly optimal best-arm identification, we show that our algorithm is $\delta$-PAC and we characterize its sample complexity. Further, we provide a lower bound on the expected number of pulls, showing that the proposed algorithm is essentially optimal up to logarithmic factors. Both upper and lower complexity bounds depend on a special definition of the associated suboptimality gap, designed in particular for the quantile bandit problem, as we show when the gap approaches zero, best-arm identification is impossible. Second, motivated by applications where the rewards are private, we provide a differentially private successive elimination algorithm whose sample complexity is finite even for distributions with infinite support-size, and we characterize its sample complexity. Our algorithms do not require prior knowledge of either the suboptimality gap or other statistical information related to the bandit problem at hand.

We study Pareto optimality in multi-objective multi-armed bandit by providing a formulation of adversarial multi-objective multi-armed bandit and properly defining its Pareto regrets that can be generalized to stochastic settings as well. The regrets do not rely on any scalarization functions and reflect Pareto optimality compared to scalarized regrets. We also present new algorithms assuming both with and without prior information of the multi-objective multi-armed bandit setting. The algorithms are shown optimal in adversarial settings and nearly optimal in stochastic settings simultaneously by our established upper bounds and lower bounds on Pareto regrets. Moreover, the lower bound analyses show that the new regrets are consistent with the existing Pareto regret for stochastic settings and extend an adversarial attack mechanism from bandit to the multi-objective one.

我们考虑使用$ K $臂的随机匪徒问题，每一个都与$ [m，m] $范围内支持的有限分布相关。我们不认为$ [m，m] $是已知的范围，并表明学习此范围有成本。确实，出现了与分销相关和无分配后悔界限之间的新权衡，这阻止了同时实现典型的$ \ ln t $和$ \ sqrt {t} $ bunds。例如，仅当与分布相关的遗憾界限至少属于$ \ sqrt {t} $的顺序时，才能实现$ \ sqrt {t} $}无分布遗憾。我们展示了一项策略，以实现新的权衡表明的遗憾。

多臂强盗（MAB）问题是增强学习领域中广泛研究的模型。本文考虑了经典mAB模型的两个案例 - 灯塔奖励分布和重尾。对于轻尾（即次高斯）案件，我们提出了UCB1-LT政策，实现了遗憾增长命令的最佳$ O（\ log t）$。对于重尾案，我们介绍了扩展的强大UCB政策，这是Bubeck等人提出的UCB政策的扩展。（2013）和Lattimore（2017）。以前的UCB政策要求在奖励分布的特定时刻了解上限的知识，在某些实际情况下可能很难获得。我们扩展的强大UCB消除了这一要求，同时仍达到最佳的遗憾增长订单$ O（\ log t）$，从而为重型奖励分配提供了扩大的UCB政策应用程序领域。

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.

本文考虑了多臂强盗（MAB）问题，并提供了一种新的最佳世界（BOBW）算法，该算法在随机和对抗性设置中几乎最佳地工作。在随机设置中，某些现有的BOBW算法获得了$ o的紧密依赖性遗憾界限（\ sum_ {i：\ delta_i> 0} \ frac {\ log t} {\ log t} {\ delta_i} {\ delta_i}）手臂$ i $和时间范围$ t $。如Audibert等。 [2007]但是，在具有低变化的臂的随机环境中，可以改善性能。实际上，他们提供了一种随机mab算法，具有$ o的差距依赖性遗憾界限t）损失方差$ \ sigma_i^2 $ a臂$ i $。在本文中，我们提出了具有差距依赖性界限的第一个BOBW算法，表明即使在可能的对抗环境中，这些方差信息也可以使用。此外，我们的间隙变量依赖性结合中的领先常数因子仅是（几乎）下界值的两倍。此外，所提出的算法在对抗环境中享有多个与数据有关的遗憾界限，并且在具有对抗性腐败的随机设置中很好地工作。所提出的算法基于以下规范化的领导方法，并采用了自适应学习率，取决于损失的经验预测误差，这导致了差距变化依赖性的遗憾界限，反映了武器的方差。

我们通过可共享的手臂设置概括了多武器的多臂土匪（MP-MAB）问题，其中几场比赛可以共享同一臂。此外，每个可共享的组都有有限的奖励能力和“每载”奖励分配，这两者都是学习者所不知道的。可共享臂的奖励取决于负载，这是“每载”奖励乘以拉动手臂的戏剧数量或当比赛数量超过容量限制时的奖励能力。当“按负载”奖励遵循高斯分布时，我们证明了样本复杂性的下限，从负载依赖的奖励中学习容量，也遗憾的是这个新的MP-MAB问题的下限。我们设计了一个容量估计器，其样品复杂性上限在奖励手段和能力方面与下限匹配。我们还提出了一种在线学习算法来解决该问题并证明其遗憾的上限。这个遗憾的上界的第一任期与遗憾的下限相同，其第二和第三个术语显然也对应于下边界。广泛的实验验证了我们算法的性能以及其在5G和4G基站选择中的增长。