我们考虑随机多武装强盗(MAB)问题,延迟影响了行动。在我们的环境中,过去采取的行动在随后的未来影响了ARM奖励。在现实世界中,行动的这种延迟影响是普遍的。例如,为某个社会群体中的人员偿还贷款的能力可能历史上历史上批准贷款申请的频率频率。如果银行将贷款申请拒绝拒绝弱势群体,则可以创建反馈循环,进一步损害该群体中获取贷款的机会。在本文中,我们制定了在多武装匪徒的背景下的行动延迟和长期影响。由于在学习期间,我们将强盗设置概括为对这种“偏置”的依赖性进行编码。目标是随着时间的推移最大化收集的公用事业,同时考虑到历史行动延迟影响所产生的动态。我们提出了一种算法,实现了$ \ tilde {\ mathcal {o}}的遗憾,并显示$ \ omega(kt ^ {2/3})$的匹配遗憾下限,其中$ k $是武器数量,$ t $是学习地平线。我们的结果通过添加技术来补充强盗文献,以处理具有长期影响的行动,并对设计公平算法有影响。
translated by 谷歌翻译
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.
translated by 谷歌翻译
富达匪徒问题是$ k $的武器问题的变体,其中每个臂的奖励通过提供额外收益的富达奖励来增强,这取决于播放器如何对该臂进行“忠诚”在过去。我们提出了两种忠诚的模型。在忠诚点模型中,额外奖励的数量取决于手臂之前播放的次数。在订阅模型中,额外的奖励取决于手臂的连续绘制的当前数量。我们考虑随机和对抗问题。由于单臂策略在随机问题中并不总是最佳,因此对抗性环境中遗憾的概念需要仔细调整。我们介绍了三个可能的遗憾和调查,这可以是偏执的偏执。我们详细介绍了增加,减少和优惠券的特殊情况(玩家在手臂的每辆M $播放后获得额外的奖励)保真奖励。对于不一定享受载体遗憾的模型,我们提供了最糟糕的下限。对于那些展示Sublinear遗憾的模型,我们提供算法并绑定他们的遗憾。
translated by 谷歌翻译
在古典语境匪徒问题中,在每轮$ 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运行一流拍卖的广告交换中模拟了我们的真实拍卖数据的算法,并表明了它们优于传统的上下文强盗算法。
translated by 谷歌翻译
在随着时间变化的组合环境中的在线决策激励,我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题,我们提供了一个通用框架,该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明,在完整信息设置下,由此产生的在线算法具有$ O(\ sqrt {t})$(近似)遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展,我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪(t^{2/3})$(近似)$(近似)的遗憾。展示了我们框架的灵活性,我们将脱机之间的转换应用于收入管理,市场设计和在线优化的几个问题,包括在线平台中的产品排名优化,拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法,例如用于最大化连续强的DR单调下调功能,这些功能受到凸约束的约束。我们表明,当应用于这些应用程序时,我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究,在这两种应用中,我们都观察到,转换的数值性能在实际情况下优于理论保证。
translated by 谷歌翻译
我们考虑使用$ K $臂的随机匪徒问题,每一个都与$ [m,m] $范围内支持的有限分布相关。我们不认为$ [m,m] $是已知的范围,并表明学习此范围有成本。确实,出现了与分销相关和无分配后悔界限之间的新权衡,这阻止了同时实现典型的$ \ ln t $和$ \ sqrt {t} $ bunds。例如,仅当与分布相关的遗憾界限至少属于$ \ sqrt {t} $的顺序时,才能实现$ \ sqrt {t} $}无分布遗憾。我们展示了一项策略,以实现新的权衡表明的遗憾。
translated by 谷歌翻译
我们介绍了一个多臂强盗模型,其中奖励是多个随机变量的总和,每个动作只会改变其中的分布。每次动作之后,代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的,在该系统中,变量代表单个客户的结果,例如点击。我们提出了UCB风格的算法,以估计基线上的动作的提升。我们研究了问题的多种变体,包括何时未知基线和受影响的变量,并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限,以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。
translated by 谷歌翻译
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)$.
translated by 谷歌翻译
我们考虑带有背包的土匪(从此以后,BWK),这是一种在供应/预算限制下的多臂土匪的通用模型。特别是,强盗算法需要解决一个众所周知的背包问题:找到最佳的物品包装到有限尺寸的背包中。 BWK问题是众多激励示例的普遍概括,范围从动态定价到重复拍卖,再到动态AD分配,再到网络路由和调度。尽管BWK的先前工作集中在随机版本上,但我们开创了可以在对手身上选择结果的另一个极端。与随机版本和“经典”对抗土匪相比,这是一个更加困难的问题,因为遗憾的最小化不再可行。相反,目的是最大程度地减少竞争比率:基准奖励与算法奖励的比率。我们设计了一种具有竞争比O(log t)的算法,相对于动作的最佳固定分布,其中T是时间范围;我们还证明了一个匹配的下限。关键的概念贡献是对问题的随机版本的新观点。我们为随机版本提出了一种新的算法,该算法是基于重复游戏中遗憾最小化的框架,并且与先前的工作相比,它具有更简单的分析。然后,我们为对抗版本分析此算法,并将其用作求解后者的子例程。
translated by 谷歌翻译
我们通过审查反馈重复进行一定的第一价格拍卖来研究在线学习,在每次拍卖结束时,出价者只观察获胜的出价,学会了适应性地出价,以最大程度地提高她的累积回报。为了实现这一目标,投标人面临着一个具有挑战性的困境:如果她赢得了竞标 - 获得正收益的唯一方法 - 然后她无法观察其他竞标者的最高竞标,我们认为我们认为这是从中汲取的。一个未知的分布。尽管这一困境让人联想到上下文强盗中的探索探索折衷权,但现有的UCB或汤普森采样算法无法直接解决。在本文中,通过利用第一价格拍卖的结构属性,我们开发了第一个实现$ o(\ sqrt {t} \ log^{2.5} t)$ hearry bund的第一个学习算法(\ sqrt {t} \ log^{2.5} t),这是最小值的最低$ $ \ log $因素,当投标人的私人价值随机生成时。我们这样做是通过在一系列问题上提供算法,称为部分有序的上下文匪徒,该算法将图形反馈跨动作,跨环境跨上下文进行结合,以及在上下文中的部分顺序。我们通过表现出一个奇怪的分离来确定该框架的优势和劣势,即在随机环境下几乎可以独立于动作/背景规模的遗憾,但是在对抗性环境下是不可能的。尽管这一通用框架有限制,但我们进一步利用了第一价格拍卖的结构,并开发了一种学习算法,该算法在存在对手生成的私有价值的情况下,在存在的情况下可以有效地运行样本(并有效地计算)。我们建立了一个$ o(\ sqrt {t} \ log^3 t)$遗憾,以此为此算法,因此提供了对第一价格拍卖的最佳学习保证的完整表征。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们考虑激励探索:一种多臂匪徒的版本,其中武器的选择由自私者控制,而算法只能发布建议。该算法控制信息流,信息不对称可以激励代理探索。先前的工作达到了最佳的遗憾率,直到乘法因素,这些因素根据贝叶斯先验而变得很大,并在武器数量上成倍规模扩展。采样每只手臂的一个更基本的问题一旦遇到了类似的因素。我们专注于激励措施的价格:出于激励兼容的目的,绩效的损失,广泛解释为。我们证明,如果用足够多的数据点初始化,则标准的匪徒汤普森采样是激励兼容的。因此,当收集这些数据点时,由于激励措施的绩效损失仅限于初始回合。这个问题主要降低到样本复杂性的问题:需要多少个回合?我们解决了这个问题,提供了匹配的上限和下限,并在各种推论中实例化。通常,最佳样品复杂性在“信念强度”中的武器数量和指数中是多项式。
translated by 谷歌翻译
我们通过可共享的手臂设置概括了多武器的多臂土匪(MP-MAB)问题,其中几场比赛可以共享同一臂。此外,每个可共享的组都有有限的奖励能力和“每载”奖励分配,这两者都是学习者所不知道的。可共享臂的奖励取决于负载,这是“每载”奖励乘以拉动手臂的戏剧数量或当比赛数量超过容量限制时的奖励能力。当“按负载”奖励遵循高斯分布时,我们证明了样本复杂性的下限,从负载依赖的奖励中学习容量,也遗憾的是这个新的MP-MAB问题的下限。我们设计了一个容量估计器,其样品复杂性上限在奖励手段和能力方面与下限匹配。我们还提出了一种在线学习算法来解决该问题并证明其遗憾的上限。这个遗憾的上界的第一任期与遗憾的下限相同,其第二和第三个术语显然也对应于下边界。广泛的实验验证了我们算法的性能以及其在5G和4G基站选择中的增长。
translated by 谷歌翻译
在线学习通常需要探索以最大程度地提高长期奖励,但这是以短期“遗憾”为代价的。我们研究如何在多个小组之间分担这种探索成本。例如,在临床试验环境中,分配了亚最佳治疗的患者有效地产生了勘探成本。当患者根据种族或年龄与自然群体相关联时,自然要问任何单一群体所承担的探索成本是否“公平”。如此有动力,我们介绍了“分组”的强盗模型。我们利用公理讨价还价的理论,尤其是纳什议价解决方案,以形式化可能构成跨群体勘探成本的公平分裂的方式。一方面,我们表明,任何遗憾的政策都引起了最不公平的结果:此类政策将在可能的情况下传递最“处于弱势”的群体。更具建设性的方式,我们得出了最佳公平且同时享受“公平价格”的政策。我们通过对华法林剂量的上下文匪徒进行案例研究来说明我们的算法框架的相对优点,我们关注多个种族和年龄段的探索成本。
translated by 谷歌翻译
我们探索了一个新的强盗实验模型,其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆,而那些执行正确的推理面部信息延迟的算法。我们的主要见解是,我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率,但是在硬性非平稳性方面显示出令人惊讶的弹性,这会导致其他自适应算法失败。
translated by 谷歌翻译
我们研究了一个顺序决策问题,其中学习者面临$ k $武装的随机匪徒任务的顺序。对手可能会设计任务,但是对手受到限制,以在$ m $ and的较小(但未知)子集中选择每个任务的最佳组。任务边界可能是已知的(强盗元学习设置)或未知(非平稳的强盗设置)。我们设计了一种基于Burnit subsodular最大化的减少的算法,并表明,在大量任务和少数最佳武器的制度中,它在两种情况下的遗憾都比$ \ tilde {o}的简单基线要小。 \ sqrt {knt})$可以通过使用为非平稳匪徒问题设计的标准算法获得。对于固定任务长度$ \ tau $的强盗元学习问题,我们证明该算法的遗憾被限制为$ \ tilde {o}(nm \ sqrt {m \ tau}+n^{2/3} m \ tau)$。在每个任务中最佳武器的可识别性的其他假设下,我们显示了一个带有改进的$ \ tilde {o}(n \ sqrt {m \ tau}+n^{1/2} {1/2} \ sqrt的强盗元学习算法{m k \ tau})$遗憾。
translated by 谷歌翻译
我们研究汤普森采样(TS)算法的遗憾,指数为家庭土匪,其中奖励分配来自一个一维指数式家庭,该家庭涵盖了许多常见的奖励分布,包括伯努利,高斯,伽玛,伽玛,指数等。我们建议汤普森采样算法,称为expts,它使用新颖的采样分布来避免估计最佳臂。我们为expts提供了严格的遗憾分析,同时产生有限的遗憾和渐近遗憾。特别是,对于带指数级家庭奖励的$ k $臂匪徒,expts of horizo​​n $ t $ sub-ucb(对于有限的时间遗憾的是问题依赖的有限时间标准) $ \ sqrt {\ log k} $,并且对于指数家庭奖励,渐近最佳。此外,我们通过在Expts中使用的采样分配外添加一个贪婪的剥削步骤,提出$^+$,以避免过度估计亚最佳武器。 expts $^+$是随时随地的强盗算法,可用于指数级的家庭奖励分布同时实现最小值和渐近最优性。我们的证明技术在概念上很简单,可以轻松地应用于用特定奖励分布分析标准的汤普森抽样。
translated by 谷歌翻译
我们在嵌套政策类别的存在下研究匪徒场景中的模型选择问题,目的是获得同时的对抗和随机性(“两全其美”)高概率的遗憾保证。我们的方法要求每个基础学习者都有一个候选人的遗憾约束,可能会或可能不会举行,而我们的元算法按照一定时间表来扮演每个基础学习者,该时间表使基础学习者的候选人后悔的界限保持平衡,直到被发现违反他们的保证为止。我们开发了专门设计的仔细的错误指定测试,以将上述模型选择标准与利用环境的(潜在良性)性质的能力相结合。我们在对抗环境中恢复畜栏算法的模型选择保证,但是在实现高概率后悔界限的附加益处,特别是在嵌套对抗性线性斑块的情况下。更重要的是,我们的模型选择结果也同时在差距假设​​下的随机环境中同时保持。这些是在(线性)匪徒场景中执行模型选择时,可以达到世界上最好的(随机和对抗性)保证的第一个理论结果。
translated by 谷歌翻译
通过新兴应用程序,如现场媒体电子商务,促销和建议,我们介绍和解决了一般的非静止多武装强盗问题,具有以下两个特征:(i)决策者可以拉动和收集每次期间,从最多$ k \,(\ ge 1)美元的奖励; (ii)手臂拉动后的预期奖励立即下降,然后随着ARM空闲时间的增加,非参数恢复。目的是最大化预期累计奖励超过$ T $时间段,我们设计了一类“纯粹的周期性政策”,共同设置了拉动每个臂的时间。对于拟议的政策,我们证明了离线问题和在线问题的性能保证。对于脱机问题,当已知所有型号参数时,所提出的周期性策略获得1- \ Mathcal O(1 / \ Sqrt {k})$的近似率,当$ k $生长时是渐近的最佳状态到无穷远。对于在线问题时,当模型参数未知并且需要动态学习时,我们将脱机周期性策略与在线策略上的上部置信程序进行集成。拟议的在线策略被证明是对脱机基准的近似拥有$ \ widetilde {\ mathcal o}(n \ sqrt {t})。我们的框架和政策设计可能在更广泛的离线规划和在线学习应用程序中阐明,具有非静止和恢复奖励。
translated by 谷歌翻译
在线强化学习(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 - 我们获得改进或新颖的样本复杂性保证。
translated by 谷歌翻译