资源限制的在线分配问题是收入管理和在线广告中的核心问题。在这些问题中,请求在有限的地平线期间顺序到达,对于每个请求,决策者需要选择消耗一定数量资源并生成奖励的动作。目标是最大限度地提高累计奖励,这是对资源总消费的限制。在本文中,我们考虑一种数据驱动的设置,其中使用决策者未知的输入模型生成每个请求的奖励和资源消耗。我们设计了一般的算法算法,可以在各种输入模型中实现良好的性能,而不知道它们面临的类型类型。特别是,我们的算法在独立和相同的分布式输入以及各种非静止随机输入模型下是渐近的最佳选择,并且当输入是对抗性时,它们达到渐近最佳的固定竞争比率。我们的算法在Lagrangian双色空间中运行:它们为使用在线镜像血管更新的每个资源维护双倍乘数。通过相应地选择参考功能,我们恢复双梯度下降和双乘法权重更新算法。与现有的在线分配问题的现有方法相比,所产生的算法简单,快速,不需要在收入函数,消费函数和动作空间中凸起。我们将应用程序讨论到网络收入管理,在线竞标,重复拍卖,预算限制,与高熵的在线比例匹配,以及具有有限库存的个性化分类优化。
translated by 谷歌翻译
在线分配资源限制问题具有丰富的运营研究历史记录。在本文中,我们介绍了\ emph {正常的在线分配问题},该变体包括用于总资源消耗的非线性规范器。在此问题中,请求多次到达,对于每个请求,决策者需要采取生成奖励和消耗资源的操作。目的是同时最大化可分离可分离的奖励和受资源限制的不可分级规范器的值。我们的主要动机是允许决策者履行可分离目标,例如与辅助,不可分配的目标的经济效率,例如分配的公平或公平。我们设计了一种简单,快速,并且具有随机I.I.D的良好性能的算法。〜和对抗的投入。特别是,我们的算法在随机I.I.D下渐近最佳。输入模型并达到固定的竞争比率,当输入是对越野的时,取决于常规管道。此外,算法和分析不需要贡献函数和消耗函数的凸起或凹面,这允许更多的模型灵活性。数值实验证实了算法在互联网广告应用中的算法和正则化的有效性。
translated by 谷歌翻译
我们研究随机的在线资源分配:决策者需要分配有限的资源来为随机生成的顺序派遣请求,以最大程度地提高奖励。通过练习,我们考虑了一个数据驱动的设置,在该设置中,请求独立于决策者未知的分布。过去已经对在线资源分配及其特殊情况进行了广泛的研究,但是这些先前的结果至关重要和普遍地依赖于一个实际上不可能的假设:请求总数(地平线)是决策者事先知道的。在许多应用程序(例如收入管理和在线广告)中,由于需求或用户流量强度的波动,请求的数量可能差异很大。在这项工作中,我们开发了在线算法,这些算法对地平线不确定性是可靠的。与已知的马环境形成鲜明对比的是,我们表明没有算法可以达到与视野不确定性无关的恒定渐近竞争比率。然后,我们引入了一种新型算法,该算法将双镜下降与精心选择的目标消耗序列结合在一起,并证明其达到了有限的竞争比率。从地平线不确定性增长时,我们的竞争比达到了最佳生长速率,我们的算法几乎是最佳的。
translated by 谷歌翻译
我们考虑一个一般的在线随机优化问题,在有限时间段的视野中具有多个预算限制。在每个时间段内,都会揭示奖励功能和多个成本功能,并且决策者需要从凸面和紧凑型措施中指定行动,以收集奖励并消耗预算。每个成本函数对应于一个预算的消费。在每个时期,奖励和成本函数都是从未知分布中得出的,该分布在整个时间内都是非平稳的。决策者的目的是最大化受预算限制的累积奖励。该配方捕获了广泛的应用程序,包括在线线性编程和网络收入管理等。在本文中,我们考虑了两个设置:(i)一个数据驱动的设置,其中真实分布未知,但可以提供先前的估计(可能不准确); (ii)一个不信息的环境,其中真实分布是完全未知的。我们提出了一项基于统一的浪费距离措施,以量化设置(i)中先验估计值的不准确性和设置(ii)中系统的非平稳性。我们表明,拟议的措施导致在两种情况下都能获得统一后悔的必要条件。对于设置(i),我们提出了一种新的算法,该算法采用了原始的偶视角,并将基础分布的先前信息集成到双重空间中的在线梯度下降过程。该算法也自然扩展到非信息设置(II)。在这两种设置下,我们显示相应的算法实现了最佳秩序的遗憾。在数值实验中,我们演示了如何将所提出的算法与重新溶解技术自然整合,以进一步提高经验性能。
translated by 谷歌翻译
本文介绍了一个基于双基的算法框架,用于求解具有累积的凸奖励,硬资源限制和不可分割的正常化程序的正规在线资源分配问题。在适应性更新资源约束的策略下,所提出的框架仅要求对经验二重性问题的近似解决方案,直到某种准确性,但在本地强烈凸出的假设下给出了最佳的对数遗憾。令人惊讶的是,对双重目标函数的微妙分析使我们能够消除遗憾的臭名昭著的日志因素。灵活的框架呈现出著名的和计算快速算法,例如双梯度下降和随机梯度下降。如果在双重优化过程中没有适应性更新,则建立了最糟糕的平方根遗憾下限,这强调了自适应双重变量更新的关键作用。全面的数值实验和实际数据应用证明了提出的算法框架的优点。
translated by 谷歌翻译
在线广告最近已发展成为一个竞争激烈且复杂的数十亿美元行业,广告商在大型和高频上竞标广告插槽。这导致对有效的“自动招标”算法的需求日益增长,这些算法确定了传入查询的投标,以最大程度地提高广告商的目标,但受其指定的约束。这项工作探讨了在日益流行的约束下,为单个价值最大化广告商提供有效的在线算法:返回式增长(ROS)。相对于最佳算法,我们对遗憾进行了量化效率,该算法知道所有查询所有查询都是先验的。我们贡献了一种简单的在线算法,该算法在期望中实现了近乎最佳的遗憾,同时始终尊重指定的ROS约束,当查询的输入顺序为i.i.d.来自某些分布的样本。我们还将结果与Balseiro,Lu和Mirrokni [BLM20]的先前工作相结合,以实现近乎最佳的遗憾,同时尊重ROS和固定的预算限制。我们的算法遵循原始的二重式框架,并使用在线镜像下降(OMD)进行双重更新。但是,我们需要使用非典型的OMD设置,因此需要使用OMD的经典低rebret保证,该保证是用于在线学习中的对抗性环境的,不再存在。尽管如此,在我们的情况下,在更普遍的情况下,在算法设计中应用低纤维动力学的情况下,OMD遇到的梯度可能远非对抗性,但受我们的算法选择的影响。我们利用这一关键见解来显示我们的OMD设置在我们的算法领域中造成了低落的遗憾。
translated by 谷歌翻译
在随着时间变化的组合环境中的在线决策激励,我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题,我们提供了一个通用框架,该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明,在完整信息设置下,由此产生的在线算法具有$ O(\ sqrt {t})$(近似)遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展,我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪(t^{2/3})$(近似)$(近似)的遗憾。展示了我们框架的灵活性,我们将脱机之间的转换应用于收入管理,市场设计和在线优化的几个问题,包括在线平台中的产品排名优化,拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法,例如用于最大化连续强的DR单调下调功能,这些功能受到凸约束的约束。我们表明,当应用于这些应用程序时,我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究,在这两种应用中,我们都观察到,转换的数值性能在实际情况下优于理论保证。
translated by 谷歌翻译
除了最大化总收入外,许多行业的决策者还希望保证跨不同资源的公平消费,并避免饱和某些资源。在这些实际需求的推动下,本文研究了基于价格的网络收入管理问题,需求学习和公平性关注不同资源的消费。我们介绍了正式的收入,即以公平的正规化为目标,作为我们的目标,将公平性纳入收入最大化目标。我们提出了一种原始的偶型在线政策,并使用受到信心限制(UCB)的需求学习方法最大化正规化收入。我们采用了几种创新技术,以使我们的算法成为连续价格集和广泛的公平规则化的统一和计算高效的框架。我们的算法实现了$ \ tilde o(n^{5/2} \ sqrt {t})$的最坏遗憾,其中$ n $表示产品数,$ t $表示时间段。一些NRM示例中的数值实验证明了我们算法在平衡收入和公平性方面的有效性。
translated by 谷歌翻译
我们研究在线学习问题,决策者必须采取一系列决策,但要受到$ M $长期约束。决策者的目标是最大程度地提高其总奖励,同时达到小累积约束,在$ t $回合中违规。我们介绍了此一般类问题的第一个最佳世界类型算法,在根据未知随机模型选择奖励和约束的情况下,无需保证,在它们的情况下,在他们的情况下选择了奖励和约束。在每个回合中由对手选择。我们的算法是关于满足长期约束的最佳固定策略的第一个在对抗环境中提供保证的算法。特别是,它保证了$ \ rho/(1+ \ rho)$的最佳奖励和额定性遗憾,其中$ \ rho $是与严格可行的解决方案有关的可行性参数。我们的框架采用传统的遗憾最小化器作为黑盒组件。因此,通过使用适当的遗憾最小化器进行实例化,它可以处理全反馈以及强盗反馈设置。此外,它允许决策者通过非凸奖励和约束无缝处理场景。我们展示了如何在重复拍卖的预算管理机制的背景下应用我们的框架,以保证不包装的长期约束(例如,ROI约束)。
translated by 谷歌翻译
我们研究了在线上下文决策问题,并具有资源约束。在每个时间段,决策者首先根据给定上下文向量预测奖励向量和资源消耗矩阵,然后解决下游优化问题以做出决策。决策者的最终目标是最大程度地利用资源消耗的奖励和效用总结,同时满足资源限制。我们提出了一种算法,该算法将基于“智能预测 - 优化(SPO)”方法的预测步骤与基于镜像下降的双重更新步骤。我们证明了遗憾的界限,并证明了我们方法的总体收敛率取决于$ \ Mathcal {o}(t^{ - 1/2})$在线镜面下降的收敛性以及使用的替代损失功能的风险范围学习预测模型。我们的算法和后悔界限适用于资源约束的一般凸的可行区域,包括硬和软资源约束案例,它们适用于广泛的预测模型,与线性上下文模型或有限策略空间的传统设置相比。我们还进行数值实验,以与传统的仅限预测方法相比,在多维背包和最长的路径实例上,与传统的仅预测方法相比,我们提出的SPO型方法的强度。
translated by 谷歌翻译
在Fisher市场中,代理商(用户)花费(人造)货币预算来购买最大化其公用事业的商品,而中央规划师则将其设定为容量约束的商品,以便市场清算。但是,定价方案在Fisher市场实现平衡结果方面的功效通常取决于用户的预算和公用事业的完全了解,并且要求交易在同时存在所有用户的静态市场中发生。结果,我们研究了Fisher市场的在线变体,其中有私人公用事业和预算参数的预算受限用户,绘制了I.I.D.从分配$ \ Mathcal {d} $,顺序输入市场。在这种情况下,我们开发了一种仅根据用户消费的观察结果来调整价格的算法用户数量和良好的能力量表为$ O(n)$。在这里,我们的遗憾措施是在线算法和离线甲骨文之间的艾森伯格 - 盖尔计划目标的最佳差距,并提供有关用户预算和公用事业的完整信息。为了确定我们方法的功效,我们证明了任何统一(静态)定价算法,包括设定预期平衡价格并完全了解分销$ \ MATHCAL {D} $的算法,既无法实现遗憾和限制的违反比$ \ omega(\ sqrt {n})$。虽然我们揭示的偏好算法不需要对分布$ \ MATHCAL {d} $不了解,但我们表明,如果$ \ Mathcal {d} $是已知的,则是预期的平衡定价Achieves $ O(\ log(\ log(n))的自适应变体)$遗憾和离散分发的恒定容量违反。最后,我们提出了数值实验,以证明相对于几个基准测试的揭示偏好算法的性能。
translated by 谷歌翻译
我们考虑带有背包的土匪(从此以后,BWK),这是一种在供应/预算限制下的多臂土匪的通用模型。特别是,强盗算法需要解决一个众所周知的背包问题:找到最佳的物品包装到有限尺寸的背包中。 BWK问题是众多激励示例的普遍概括,范围从动态定价到重复拍卖,再到动态AD分配,再到网络路由和调度。尽管BWK的先前工作集中在随机版本上,但我们开创了可以在对手身上选择结果的另一个极端。与随机版本和“经典”对抗土匪相比,这是一个更加困难的问题,因为遗憾的最小化不再可行。相反,目的是最大程度地减少竞争比率:基准奖励与算法奖励的比率。我们设计了一种具有竞争比O(log t)的算法,相对于动作的最佳固定分布,其中T是时间范围;我们还证明了一个匹配的下限。关键的概念贡献是对问题的随机版本的新观点。我们为随机版本提出了一种新的算法,该算法是基于重复游戏中遗憾最小化的框架,并且与先前的工作相比,它具有更简单的分析。然后,我们为对抗版本分析此算法,并将其用作求解后者的子例程。
translated by 谷歌翻译
我们探索了一个新的强盗实验模型,其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆,而那些执行正确的推理面部信息延迟的算法。我们的主要见解是,我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率,但是在硬性非平稳性方面显示出令人惊讶的弹性,这会导致其他自适应算法失败。
translated by 谷歌翻译
带背包(BWK)的匪徒是供应/预算约束下的多武装匪徒的一般模型。虽然BWK的最坏情况遗憾的遗憾是良好的理解,但我们提出了三种结果,超出了最坏情况的观点。首先,我们提供上下界限,其数量为对数,实例相关的后悔率的完整表征。其次,我们考虑BWK中的“简单遗憾”,在给定回合追踪算法的性能,并证明它在除了几轮之外的一切。第三,我们提供从BWK到匪徒的一般“减少”,这利用了一些已知的有用结构,并将这种减少应用于组合半刺点,线性上下文匪徒和多项式登录匪徒。我们的成果从\ CiteT {AgraWaldevanur-EC14}的BWK算法构建,提供了新的分析。
translated by 谷歌翻译
在这项工作中,我们研究了数据驱动的决策,并偏离了经典的相同和独立分布(I.I.D.)假设。我们提出了一个新的框架,其中我们将历史样本从未知和不同的分布中产生,我们将其配置为异质环境。假定这些分布位于具有已知半径的异质球中,并围绕(也是)未知的未来(样本外)分布,将评估决策的表现。我们量化了中央数据驱动的策略(例如样本平均近似值,也可以通过速率优势)来量化的渐近性最坏案例遗憾,这是异质性球半径的函数。我们的工作表明,在问题类别和异质性概念的不同组合中,可实现的性能类型的变化很大。我们通过比较广泛研究的数据驱动问题(例如定价,滑雪租赁和新闻顾问)的异质版本来证明框架的多功能性。在途中,我们在数据驱动的决策和分配强大的优化之间建立了新的联系。
translated by 谷歌翻译
本文重点介绍了静态和时变设置中决策依赖性分布的随机鞍点问题。这些是目标是随机收益函数的预期值,其中随机变量从分布图引起的分布中绘制。对于一般分布地图,即使已知分布是已知的,发现鞍点的问题也是一般的计算繁琐。为了实现易求解的解决方案方法,我们介绍了均衡点的概念 - 这是它们诱导的静止随机最小值问题的马鞍点 - 并为其存在和唯一性提供条件。我们证明,两个类解决方案之间的距离被界定,条件是该目标具有强凸强 - 凹入的收益和Lipschitz连续分布图。我们开发确定性和随机的原始算法,并证明它们对均衡点的收敛性。特别是,通过将来自随机梯度估计器的出现的错误建模为子-Weibull随机变量,我们提供期望的错误界限,并且在每个迭代的高概率中提供的误差;此外,我们向期望和几乎肯定地显示给社区的融合。最后,我们调查了分布地图的条件 - 我们调用相反的混合优势 - 确保目标是强烈的凸强 - 凹陷的。在这种假设下,我们表明原始双算法以类似的方式汇集到鞍座点。
translated by 谷歌翻译
We study the classical Network Revenue Management (NRM) problem with accept/reject decisions and $T$ IID arrivals. We consider a distributional form where each arrival must fall under a finite number of possible categories, each with a deterministic resource consumption vector, but a random value distributed continuously over an interval. We develop an online algorithm that achieves $O(\log^2 T)$ regret under this model, with no further assumptions. We develop another online algorithm that achieves an improved $O(\log T)$ regret, with only a second-order growth assumption. To our knowledge, these are the first results achieving logarithmic-level regret in a continuous-distribution NRM model without further "non-degeneracy" assumptions. Our results are achieved via new techniques including: a new method of bounding myopic regret, a "semi-fluid" relaxation of the offline allocation, and an improved bound on the "dual convergence".
translated by 谷歌翻译
我们通过反馈信息研究了离线和在线上下文优化的问题,而不是观察损失,我们会在事后观察到最佳的动作,而是对目标功能充分了解的甲骨文。我们的目标是最大程度地减少遗憾,这被定义为我们的损失与全知的甲骨所产生的损失之间的区别。在离线设置中,决策者可以从过去段中获得信息,并且需要做出一个决策,而在在线环境中,决策者在每个时期内都会动态地基于一组新的可行动作和上下文功能,以动态进行决策。 。对于离线设置,我们表征了最佳的最小策略,确定可以实现的性能,这是数据引起的信息的基础几何形状的函数。在在线环境中,我们利用这种几何表征来优化累积遗憾。我们开发了一种算法,该算法在时间范围内产生了对数的第一个遗憾。
translated by 谷歌翻译
我们系统地研究了在乐观学习的背景下将整个文件存储在容量有限的缓存中的问题,在这种学习情况下,缓存策略可以访问预测甲骨文(例如,由神经网络提供)。连续的文件请求假定由对手生成,并且对Oracle的准确性没有任何假设。在这种情况下,我们为预测辅助在线缓存提供了通用的下限,并继续设计一套具有一系列性能复杂性权衡的政策。所有提议的政策都均均与甲骨文的准确性相称。我们的结果大大改善了所有最近提供的在线缓存政策,该政策无法利用Oracle预测,仅提供$ O(\ sqrt {t})$遗憾。在这种追求中,我们据我们所知,我们设计了第一个全面的乐观跟随领导者政策,该政策超出了缓存问题。我们还研究了具有不同尺寸的缓存文件和两部分网络缓存问题的问题。最后,我们通过使用现实世界痕迹进行广泛的数值实验来评估所提出的策略的功效。
translated by 谷歌翻译
我们研究一种在线线性编程(OLP)问题,该问题通过随机输入最大化目标函数。当随机输入遵循一些I.I.D分布时,对分析此类OLP的各种算法的性能进行了充分的研究。要问的两个核心问题是:(i)算法如果随机输入不是I.I.D而是静止的,并且(ii)如果我们知道随机输入是潮流的,那么我们如何修改我们的算法,因此,该算法可以达到相同的效率。固定。我们通过分析再生类型的输入类型来回答第一个问题,并表明两种流行算法的遗憾与其I.I.D对应物相同的顺序界定。我们讨论了线性增长的输入的背景下的第二个问题,并提出了两种趋势自适应算法。我们提供数值仿真,以说明在再生和时尚输入下算法的性能。
translated by 谷歌翻译