最近，提出了经典多军强盗的多代理变体来解决在线学习中的公平问题。受社会选择和经济学方面的长期工作的启发，目标是优化NASH的社会福利，而不是全面的效用。不幸的是，就回合$ t $的数量而言，以前的算法要么不是有效的，要么实现次级遗憾。我们提出了一种新的有效算法，其遗憾也比以前效率低下的算法要低。对于$ n $ agents，$ k $ ands和$ t $ rounds，我们的方法遗憾的是$ \ tilde {o}（\ sqrt {nkt} + nk）$。这是对先前方法的改进，后者对$ \ tilde {o}（\ min（nk，\ sqrt {n} k^{3/2}）\ sqrt {t}）$的遗憾。我们还使用$ \ tilde {o}（\ sqrt {kt} + n^2k）$遗憾的方法来补充有效算法。实验发现证实了与先前方法相比，我们有效算法的有效性。

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

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

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}））$上限。进行数值实验以说明理论发现。我们的结果揭示了对一致性和轻尾风险之间不兼容的见解，而这表明对预期的遗憾和轻尾风险的最佳最佳性是兼容的。

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

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

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.

In this paper we study the contextual bandit problem (also known as the multi-armed bandit problem with expert advice) for linear payoff functions. For T rounds, K actions, and d dimensional feature vectors, we prove an O T d ln 3 (KT ln(T )/δ) regret bound that holds with probability 1 − δ for the simplest known (both conceptually and computationally) efficient upper confidence bound algorithm for this problem. We also prove a lower bound of Ω( √ T d) for this setting, matching the upper bound up to logarithmic factors.

我们研究了标准匪徒问题的扩展，其中有很多专家。多层专家按一层进行选择，只有最后一层的专家才能发挥作用。学习政策的目的是最大程度地减少该等级专家环境中的遗憾。我们首先分析了总遗憾随着层数线性增长的案例。然后，我们关注的是所有专家都在施加上层信心（UCB）策略，并在不同情况下给出了几个子线上界限。最后，我们设计了一些实验，以帮助对分层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索引以及自适应阈值值。

在本文中，我们考虑了在规避风险的标准下线性收益的上下文多臂强盗问题。在每个回合中，每个手臂都会揭示上下文，决策者选择一只手臂拉动并获得相应的奖励。特别是，我们将均值变化视为风险标准，最好的组是具有最大均值奖励的均值。我们将汤普森采样算法应用于脱节模型，并为提出算法的变体提供全面的遗憾分析。对于$ 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 $。我们提出的算法的经验性能通过投资组合选择问题来证明。

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

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.

我们考虑一个多武装的强盗设置，在每一轮的开始时，学习者接收嘈杂的独立，并且可能偏见，\ emph {评估}每个臂的真正奖励，它选择$ k $武器的目标累积尽可能多的奖励超过$ $ rounds。在假设每轮在每个臂的真正奖励从固定分发中汲取的，我们得出了不同的算法方法和理论保证，具体取决于评估的生成方式。首先，在观察功能是真正奖励的遗传化线性函数时，我们在一般情况下展示$ \ widetilde {o}（t ^ {2/3}）$后悔。另一方面，当观察功能是真正奖励的嘈杂线性函数时，我们就可以派生改进的$ \ widetilde {o}（\ sqrt {t}）$后悔。最后，我们报告了一个实证验证，确认我们的理论发现，与替代方法进行了彻底的比较，并进一步支持在实践中实现这一环境的兴趣。

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

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

在线学习算法广泛用于网络上的搜索和内容优化，必须平衡探索和开发，可能牺牲当前用户的经验，以获得将来会导致未来更好决策的信息。虽然在最坏的情况下，与贪婪算法相比，显式探索具有许多缺点，其通过选择当前看起来最佳的动作始终“利用”。我们在数据中固有的多样性的情况下提出了明确的探索不必要。我们在最近的一系列工作中进行了线性上下围匪盗模型中贪婪算法的平滑分析。我们提高了先前的结果，表明，只要多样性条件保持，贪婪的方法几乎符合任何其他算法的最佳可能性贝叶斯遗憾率，并且这种遗憾是最多的$ \ tilde o（t ^ {1/ 3}）$。

合作匪徒问题越来越多地成为其在大规模决策中的应用。然而，对此问题的大多数研究专注于具有完美通信的环境，而在大多数现实世界分布式设置中，通信通常是随机网络，具有任意损坏和延迟。在本文中，我们在三个典型的真实沟通场景下研究了合作匪徒学习，即（a）通过随机时变网络的消息传递，（b）通过随机延迟的网络瞬时奖励共享（c ）通过对冲损坏的奖励来传递消息，包括拜占庭式沟通。对于每个环境中的每一个，我们提出了实现竞争性能的分散算法，以及在发生的群体后悔的近乎最佳保证。此外，在具有完美通信的环境中，我们提出了一种改进的延迟更新算法，其优于各种网络拓扑的现有最先进的算法。最后，我们在集团后悔呈现紧密的网络依赖性最低限度。我们所提出的算法很简单，以实现和获得竞争性的经验性能。

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