大多数在线平台都在努力从与用户的互动中学习,许多人从事探索:为了获取新信息而做出潜在的次优选择。我们研究探索与竞争之间的相互作用:这样的平台如何平衡学习探索和用户的竞争。在这里,用户扮演三个不同的角色:他们是产生收入的客户,他们是学习的数据来源,并且是自私的代理商,可以在竞争平台中进行选择。我们考虑了一种风格化的双重垄断模型,其中两家公司面临着相同的多军强盗问题。用户一一到达,并在两家公司之间进行选择,因此,只有在选择它的情况下,每个公司都在其强盗问题上取得进展。通过理论结果和数值模拟的混合,我们研究了竞争是否会激发更好的Bandit算法的采用,以及它是否导致用户增加福利。我们发现,Stark竞争会导致公司致力于导致低福利的“贪婪”强盗算法。但是,通过向公司提供一些“免费”用户来激励更好的探索策略并增加福利来削弱竞争。我们调查了削弱竞争的两个渠道:放松用户的理性并为一家公司带来首次推广优势。我们的发现与“竞争与创新”关系密切相关,并阐明了数字经济中的第一步优势。
translated by 谷歌翻译
我们考虑激励探索:一种多臂匪徒的版本,其中武器的选择由自私者控制,而算法只能发布建议。该算法控制信息流,信息不对称可以激励代理探索。先前的工作达到了最佳的遗憾率,直到乘法因素,这些因素根据贝叶斯先验而变得很大,并在武器数量上成倍规模扩展。采样每只手臂的一个更基本的问题一旦遇到了类似的因素。我们专注于激励措施的价格:出于激励兼容的目的,绩效的损失,广泛解释为。我们证明,如果用足够多的数据点初始化,则标准的匪徒汤普森采样是激励兼容的。因此,当收集这些数据点时,由于激励措施的绩效损失仅限于初始回合。这个问题主要降低到样本复杂性的问题:需要多少个回合?我们解决了这个问题,提供了匹配的上限和下限,并在各种推论中实例化。通常,最佳样品复杂性在“信念强度”中的武器数量和指数中是多项式。
translated by 谷歌翻译
众所周知,传统平台之间的竞争可以通过将平台的操作与用户偏好保持一致,从而改善用户实用性。但是,在数据驱动的市场中表现出多大的一致性?为了从理论的角度研究这个问题,我们介绍了一个双重垄断市场,平台动作是强盗算法,两个平台竞争用户参与。该市场的一个显着特征是,建议的质量取决于强盗算法和用户交互提供的数据量。算法性能与用户的动作之间的这种相互依赖性使市场平衡的结构及其在用户公用事业方面的质量复杂化。我们的主要发现是,该市场的竞争并不能完全使市场成果与用户公用事业完全融合。有趣的是,市场成果不仅在平台拥有单独的数据存储库时,而且在平台具有共享数据存储库时表现不对。尽管如此,数据共享假设会影响什么机制驱动未对准的机制,并影响未对准的特定形式(例如,最佳案例和最差的市场成果的质量)。从更广泛的角度来看,我们的工作说明了数字市场中的竞争对用户实用性产生了微妙的后果,值得进一步调查。
translated by 谷歌翻译
在线学习算法广泛用于网络上的搜索和内容优化,必须平衡探索和开发,可能牺牲当前用户的经验,以获得将来会导致未来更好决策的信息。虽然在最坏的情况下,与贪婪算法相比,显式探索具有许多缺点,其通过选择当前看起来最佳的动作始终“利用”。我们在数据中固有的多样性的情况下提出了明确的探索不必要。我们在最近的一系列工作中进行了线性上下围匪盗模型中贪婪算法的平滑分析。我们提高了先前的结果,表明,只要多样性条件保持,贪婪的方法几乎符合任何其他算法的最佳可能性贝叶斯遗憾率,并且这种遗憾是最多的$ \ tilde o(t ^ {1/ 3})$。
translated by 谷歌翻译
我们考虑带有背包的土匪(从此以后,BWK),这是一种在供应/预算限制下的多臂土匪的通用模型。特别是,强盗算法需要解决一个众所周知的背包问题:找到最佳的物品包装到有限尺寸的背包中。 BWK问题是众多激励示例的普遍概括,范围从动态定价到重复拍卖,再到动态AD分配,再到网络路由和调度。尽管BWK的先前工作集中在随机版本上,但我们开创了可以在对手身上选择结果的另一个极端。与随机版本和“经典”对抗土匪相比,这是一个更加困难的问题,因为遗憾的最小化不再可行。相反,目的是最大程度地减少竞争比率:基准奖励与算法奖励的比率。我们设计了一种具有竞争比O(log t)的算法,相对于动作的最佳固定分布,其中T是时间范围;我们还证明了一个匹配的下限。关键的概念贡献是对问题的随机版本的新观点。我们为随机版本提出了一种新的算法,该算法是基于重复游戏中遗憾最小化的框架,并且与先前的工作相比,它具有更简单的分析。然后,我们为对抗版本分析此算法,并将其用作求解后者的子例程。
translated by 谷歌翻译
当他们更喜欢$ \ texit {exploit} $时,您如何激励自我兴趣的代理到$ \ texit {探索} $?我们考虑复杂的探索问题,其中每个代理面临相同(但未知)MDP。与传统的加固学习配方相比,代理商控制了政策的选择,而算法只能发出建议。然而,该算法控制信息流,并且可以通过信息不对称激励代理探索。我们设计一种算法,探讨MDP中的所有可达状态。我们达到了类似于先前研究的静态,无国籍探索问题中激励探索的保证担保。据我们所知,这是第一个考虑在有状态,强化学习环境中设计的工作。
translated by 谷歌翻译
我们探索了一个新的强盗实验模型,其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆,而那些执行正确的推理面部信息延迟的算法。我们的主要见解是,我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率,但是在硬性非平稳性方面显示出令人惊讶的弹性,这会导致其他自适应算法失败。
translated by 谷歌翻译
我们为依次随机实验提出了一种新的扩散 - 反应分析,包括在解决多臂匪徒问题中出现的扩散分析。在使用$ n $时间步骤的实验中,我们让动作规模之间的平均奖励差距到$ 1/\ sqrt {n} $,以将学习任务的难度保留为$ n $的增长。在这个方案中,我们表明,一类顺序随机的马尔可夫实验的行为收敛到扩散极限,作为对随机微分方程的解决方案。因此,扩散极限使我们能够得出顺序实验的随机动力学的精致实例特异性表征。我们使用扩散极限来获得一些关于顺序实验的遗憾和信念演变的新见解,包括汤普森采样。一方面,我们表明,当奖励差距相对较大时,所有随机概率的顺序实验都具有lipchitz连续的依赖性。另一方面,我们发现,汤普森(Thompson)的样本具有渐近性的先验差异,达到了近乎特定实例的遗憾缩放,包括较大的奖励差距。但是,尽管使用非信息先验对汤普森采样产生了良好的遗憾,但我们表明,随着时间的流逝,诱发的后验信仰非常不稳定。
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 谷歌翻译
带背包(BWK)的匪徒是供应/预算约束下的多武装匪徒的一般模型。虽然BWK的最坏情况遗憾的遗憾是良好的理解,但我们提出了三种结果,超出了最坏情况的观点。首先,我们提供上下界限,其数量为对数,实例相关的后悔率的完整表征。其次,我们考虑BWK中的“简单遗憾”,在给定回合追踪算法的性能,并证明它在除了几轮之外的一切。第三,我们提供从BWK到匪徒的一般“减少”,这利用了一些已知的有用结构,并将这种减少应用于组合半刺点,线性上下文匪徒和多项式登录匪徒。我们的成果从\ CiteT {AgraWaldevanur-EC14}的BWK算法构建,提供了新的分析。
translated by 谷歌翻译
我们研究Stackelberg游戏,其中一位校长反复与长寿,非洋流代理商进行互动,而不知道代理商的回报功能。尽管当代理商是近视,非侧心代理会带来额外的并发症时,在Stackelberg游戏中的学习是充分理解的。尤其是,非洋流代理可以从战略上选择当前劣等的行动,以误导校长的学习算法并在未来获得更好的结果。我们提供了一个通用框架,该框架可在存在近视剂的情况下降低非洋白酶的学习来优化强大的匪徒。通过设计和分析微型反应性匪徒算法,我们的还原从校长学习算法的统计效率中进行了差异,以与其在诱导接近最佳的响应中的有效性。我们将此框架应用于Stackelberg Security Games(SSG),需求曲线,战略分类和一般有限的Stackelberg游戏的价格。在每种情况下,我们都表征了近最佳响应中存在的错误的类型和影响,并为此类拼写错误开发了一种鲁棒性的学习算法。在此过程中,我们通过最先进的$ O(n^3)$从SSGS中提高了SSG中的学习复杂性,从通过发现此类游戏的基本结构属性。该结果除了对非洋流药物学习之外,还具有独立的兴趣。
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 谷歌翻译
考虑在线学习算法同时做出决策并从反馈中学习。此类算法被广泛部署在产品和数字内容的推荐系统中。本文展示了在线学习算法偏见的偏低替代方案,以及它如何塑造建议系统的需求。首先,我们考虑$ k $武装的土匪。我们证明,$ \ varepsilon $ - 果岭选择一个无风险的手臂,而不是一个具有均等预期奖励的风险臂,概率是任意接近一个的概率。这是对不良奖励估计的武器采样的结果。通过实验,我们表明其他在线学习算法也表现出风险规避。在推荐系统环境中,我们表明,该算法对用户的嘈杂奖励减少的内容受到算法的青睐。结合使战略内容创建者朝着相似的预期质量的内容驱动战略性创建者的平衡力,对内容的优势不一定更好,挥发性较小,被夸大了。
translated by 谷歌翻译
富达匪徒问题是$ k $的武器问题的变体,其中每个臂的奖励通过提供额外收益的富达奖励来增强,这取决于播放器如何对该臂进行“忠诚”在过去。我们提出了两种忠诚的模型。在忠诚点模型中,额外奖励的数量取决于手臂之前播放的次数。在订阅模型中,额外的奖励取决于手臂的连续绘制的当前数量。我们考虑随机和对抗问题。由于单臂策略在随机问题中并不总是最佳,因此对抗性环境中遗憾的概念需要仔细调整。我们介绍了三个可能的遗憾和调查,这可以是偏执的偏执。我们详细介绍了增加,减少和优惠券的特殊情况(玩家在手臂的每辆M $播放后获得额外的奖励)保真奖励。对于不一定享受载体遗憾的模型,我们提供了最糟糕的下限。对于那些展示Sublinear遗憾的模型,我们提供算法并绑定他们的遗憾。
translated by 谷歌翻译
在线学习通常需要探索以最大程度地提高长期奖励,但这是以短期“遗憾”为代价的。我们研究如何在多个小组之间分担这种探索成本。例如,在临床试验环境中,分配了亚最佳治疗的患者有效地产生了勘探成本。当患者根据种族或年龄与自然群体相关联时,自然要问任何单一群体所承担的探索成本是否“公平”。如此有动力,我们介绍了“分组”的强盗模型。我们利用公理讨价还价的理论,尤其是纳什议价解决方案,以形式化可能构成跨群体勘探成本的公平分裂的方式。一方面,我们表明,任何遗憾的政策都引起了最不公平的结果:此类政策将在可能的情况下传递最“处于弱势”的群体。更具建设性的方式,我们得出了最佳公平且同时享受“公平价格”的政策。我们通过对华法林剂量的上下文匪徒进行案例研究来说明我们的算法框架的相对优点,我们关注多个种族和年龄段的探索成本。
translated by 谷歌翻译
经验和实验证据表明,人工智能算法学会收取超竞争价格。在本文中,我们开发了一种理论模型来通过自适应学习算法研究勾结。使用流体近似技术,我们表征了一般游戏的连续时间学习成果,并确定勾结的主要驱动力:协调偏见。在一个简单的主导策略游戏中,我们展示了算法估计之间的相关性如何导致持续的偏见,从长远来看持续犯罪行动。我们证明,使用反事实收益来告知其更新的算法避免了这种偏见并融合了主导策略。我们设计了一种带有反馈的机制:设计师揭示了事前信息以帮助反事实计算。我们表明,这种机制实现了社会最佳。最后,我们将我们的框架应用于文献中研究和拍卖的两个模拟,并分析结果合理化。
translated by 谷歌翻译
我们介绍了一个多臂强盗模型,其中奖励是多个随机变量的总和,每个动作只会改变其中的分布。每次动作之后,代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的,在该系统中,变量代表单个客户的结果,例如点击。我们提出了UCB风格的算法,以估计基线上的动作的提升。我们研究了问题的多种变体,包括何时未知基线和受影响的变量,并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限,以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。
translated by 谷歌翻译
在随着时间变化的组合环境中的在线决策激励,我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题,我们提供了一个通用框架,该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明,在完整信息设置下,由此产生的在线算法具有$ O(\ sqrt {t})$(近似)遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展,我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪(t^{2/3})$(近似)$(近似)的遗憾。展示了我们框架的灵活性,我们将脱机之间的转换应用于收入管理,市场设计和在线优化的几个问题,包括在线平台中的产品排名优化,拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法,例如用于最大化连续强的DR单调下调功能,这些功能受到凸约束的约束。我们表明,当应用于这些应用程序时,我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究,在这两种应用中,我们都观察到,转换的数值性能在实际情况下优于理论保证。
translated by 谷歌翻译
在拍卖领域,了解重复拍卖中学习动态的收敛属性是一个及时,重要的问题,例如在线广告市场中有许多应用程序。这项工作着重于重复的首次价格拍卖,该物品具有固定值的竞标者学会使用基于平均值的算法出价 - 大量的在线学习算法,其中包括流行的无regret算法,例如多重权重更新,并遵循扰动的领导者。我们完全表征了基于均值算法的学习动力学,从收敛到拍卖的NASH平衡方面,具有两种感觉:(1)时间平均水平:竞标者在bidiper the NASH平衡方面的回合分数,在极限中均在极限中。 ; (2)最后一题:竞标者的混合策略概况接近限制的NASH平衡。具体而言,结果取决于最高值的投标人的数量: - 如果数量至少为三个,则竞标动力学几乎可以肯定地收敛到拍卖的NASH平衡,无论是在时间平时还是在最后近期的情况下。 - 如果数字为两个,则竞标动力学几乎可以肯定会在时间平时收敛到NASH平衡,但不一定在最后近期。 - 如果数字是一个,则竞标动力学可能不会在时间平均值或最后近期的时间内收敛到NASH平衡。我们的发现为学习算法的融合动力学研究开辟了新的可能性。
translated by 谷歌翻译
我们考虑随机多武装强盗(MAB)问题,延迟影响了行动。在我们的环境中,过去采取的行动在随后的未来影响了ARM奖励。在现实世界中,行动的这种延迟影响是普遍的。例如,为某个社会群体中的人员偿还贷款的能力可能历史上历史上批准贷款申请的频率频率。如果银行将贷款申请拒绝拒绝弱势群体,则可以创建反馈循环,进一步损害该群体中获取贷款的机会。在本文中,我们制定了在多武装匪徒的背景下的行动延迟和长期影响。由于在学习期间,我们将强盗设置概括为对这种“偏置”的依赖性进行编码。目标是随着时间的推移最大化收集的公用事业,同时考虑到历史行动延迟影响所产生的动态。我们提出了一种算法,实现了$ \ tilde {\ mathcal {o}}的遗憾,并显示$ \ omega(kt ^ {2/3})$的匹配遗憾下限,其中$ k $是武器数量,$ t $是学习地平线。我们的结果通过添加技术来补充强盗文献,以处理具有长期影响的行动,并对设计公平算法有影响。
translated by 谷歌翻译