我们考虑一个一般的在线随机优化问题,在有限时间段的视野中具有多个预算限制。在每个时间段内,都会揭示奖励功能和多个成本功能,并且决策者需要从凸面和紧凑型措施中指定行动,以收集奖励并消耗预算。每个成本函数对应于一个预算的消费。在每个时期,奖励和成本函数都是从未知分布中得出的,该分布在整个时间内都是非平稳的。决策者的目的是最大化受预算限制的累积奖励。该配方捕获了广泛的应用程序,包括在线线性编程和网络收入管理等。在本文中,我们考虑了两个设置:(i)一个数据驱动的设置,其中真实分布未知,但可以提供先前的估计(可能不准确); (ii)一个不信息的环境,其中真实分布是完全未知的。我们提出了一项基于统一的浪费距离措施,以量化设置(i)中先验估计值的不准确性和设置(ii)中系统的非平稳性。我们表明,拟议的措施导致在两种情况下都能获得统一后悔的必要条件。对于设置(i),我们提出了一种新的算法,该算法采用了原始的偶视角,并将基础分布的先前信息集成到双重空间中的在线梯度下降过程。该算法也自然扩展到非信息设置(II)。在这两种设置下,我们显示相应的算法实现了最佳秩序的遗憾。在数值实验中,我们演示了如何将所提出的算法与重新溶解技术自然整合,以进一步提高经验性能。
translated by 谷歌翻译
资源限制的在线分配问题是收入管理和在线广告中的核心问题。在这些问题中,请求在有限的地平线期间顺序到达,对于每个请求,决策者需要选择消耗一定数量资源并生成奖励的动作。目标是最大限度地提高累计奖励,这是对资源总消费的限制。在本文中,我们考虑一种数据驱动的设置,其中使用决策者未知的输入模型生成每个请求的奖励和资源消耗。我们设计了一般的算法算法,可以在各种输入模型中实现良好的性能,而不知道它们面临的类型类型。特别是,我们的算法在独立和相同的分布式输入以及各种非静止随机输入模型下是渐近的最佳选择,并且当输入是对抗性时,它们达到渐近最佳的固定竞争比率。我们的算法在Lagrangian双色空间中运行:它们为使用在线镜像血管更新的每个资源维护双倍乘数。通过相应地选择参考功能,我们恢复双梯度下降和双乘法权重更新算法。与现有的在线分配问题的现有方法相比,所产生的算法简单,快速,不需要在收入函数,消费函数和动作空间中凸起。我们将应用程序讨论到网络收入管理,在线竞标,重复拍卖,预算限制,与高熵的在线比例匹配,以及具有有限库存的个性化分类优化。
translated by 谷歌翻译
本文介绍了一个基于双基的算法框架,用于求解具有累积的凸奖励,硬资源限制和不可分割的正常化程序的正规在线资源分配问题。在适应性更新资源约束的策略下,所提出的框架仅要求对经验二重性问题的近似解决方案,直到某种准确性,但在本地强烈凸出的假设下给出了最佳的对数遗憾。令人惊讶的是,对双重目标函数的微妙分析使我们能够消除遗憾的臭名昭著的日志因素。灵活的框架呈现出著名的和计算快速算法,例如双梯度下降和随机梯度下降。如果在双重优化过程中没有适应性更新,则建立了最糟糕的平方根遗憾下限,这强调了自适应双重变量更新的关键作用。全面的数值实验和实际数据应用证明了提出的算法框架的优点。
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 谷歌翻译
本文在动态定价的背景下调查预先存在的离线数据对在线学习的影响。我们在$ t $期间的销售地平线上研究单一产品动态定价问题。每个时段的需求由产品价格根据具有未知参数的线性需求模型确定。我们假设在销售地平线开始之前,卖方已经有一些预先存在的离线数据。离线数据集包含$ N $示例,其中每个标准是由历史价格和相关的需求观察组成的输入输出对。卖方希望利用预先存在的离线数据和顺序在线数据来最大限度地减少在线学习过程的遗憾。我们的特征在于在线学习过程的最佳遗憾的脱机数据的大小,位置和分散的联合效果。具体而言,离线数据的大小,位置和色散由历史样本数量为$ n $,平均历史价格与最佳价格$ \ delta $之间的距离以及历史价格的标准差价Sigma $分别。我们表明最佳遗憾是$ \ widetilde \ theta \ left(\ sqrt {t} \ wedge \ frac {t} {(n \ wedge t)\ delta ^ 2 + n \ sigma ^ 2} \右)$,基于“面对不确定性”原则的“乐观主义”的学习算法,其遗憾是最佳的对数因子。我们的结果揭示了对脱机数据的大小的最佳遗憾率的惊人变换,我们称之为阶段转型。此外,我们的结果表明,离线数据的位置和分散也对最佳遗憾具有内在效果,我们通过逆平面法量化了这种效果。
translated by 谷歌翻译
我们在广义线性需求模型下考虑与协变量的动态定价问题:卖方可以在$ T $时间段的地平线上动态调整产品的价格,并在每次$ T $时,产品的需求是通过未知的广义线性模型共同由价格和可观察的协变量矢量$ x_t \ in \ mathbb {r} ^ d $。现有文献中的大多数假设协变量矢量$ X_T $的独立和相同分布(i.i.d.);少数论文放松这种假设牺牲模型一般性或产生了次优遗憾的界限。在本文中,我们显示简单的定价算法有$ O(D \ SQRT {T} \ log t)$后悔上限而不假设协变量上的任何统计结构$ x_t $(甚至可以任意选择)。遗憾的上限与对数因子的下限(即使是i.i.d.假设)匹配。我们的论文如此表明(i)i.i.d.获得低遗憾的假设是不需要的,(ii)遗憾的遗憾可以独立于$ x_t $'s的协方差矩阵的(逆)最小特征值,以往的界限。此外,我们讨论了一个更好的遗憾,可以实现更好的遗憾以及如何应用汤普森采样算法来提供价格的有效计算。
translated by 谷歌翻译
我们考虑具有未知实用程序参数的多项式logit模型(MNL)下的动态分类优化问题。本文研究的主要问题是$ \ varepsilon $ - 污染模型下的模型错误指定,该模型是强大统计和机器学习中的基本模型。特别是,在整个长度$ t $的销售范围内,我们假设客户根据$(1- \ varepsilon)$ - 时间段的$(1- \ varepsilon)的基础多项式logit选择模型进行购买,并进行任意购买取而代之的是在剩余的$ \ varepsilon $ - 分数中的决策。在此模型中,我们通过主动淘汰策略制定了新的强大在线分类优化政策。我们对遗憾建立上限和下界,并表明当分类能力恒定时,我们的政策是$ t $的最佳对数因素。分类能力具有恒定的上限。我们进一步制定了一种完全自适应策略,该政策不需要任何先验知识,即污染参数$ \ varepsilon $。如果存在最佳和亚最佳产品之间存在的亚临时差距,我们还建立了依赖差距的对数遗憾上限和已知的 - $ \ VAREPSILON $和UNKNOWER-$ \ \ VAREPSILON $案例。我们的仿真研究表明,我们的政策表现优于基于上置信度范围(UCB)和汤普森采样的现有政策。
translated by 谷歌翻译
价格歧视,这是指为不同客户群体的不同价格进行规定的策略,已广泛用于在线零售。虽然它有助于提高在线零售商的收入,但它可能会对公平产生严重关切,甚至违反了监管和法律。本文研究了公平限制下动态歧视性定价的问题。特别是,我们考虑一个有限的销售长度$ T $的单一产品,为一组客户提供两组客户。每组客户都有其未知的需求功能,需要学习。对于每个销售期间,卖方确定每组的价格并观察其购买行为。虽然现有文学主要侧重于最大化收入,但在动态定价文学中确保不同客户的公平尚未完全探索。在这项工作中,我们采用了(Cohen等人)的公平概念。对于价格公平性,我们在遗憾方面提出了最佳的动态定价政策,从而强制执行严格的价格公平制约。与标准$ \ sqrt {t} $ - 在线学习中的遗憾遗憾,我们表明我们案例中的最佳遗憾是$ \ tilde {\ theta}(t ^ {4/5})$。我们进一步将算法扩展到更普遍的公平概念,包括作为一个特例的需求公平。为了处理这一普通类,我们提出了一个柔和的公平约束,并开发了实现$ \ tilde {o}(t ^ {4/5})$后悔的动态定价政策。
translated by 谷歌翻译
在线分配资源限制问题具有丰富的运营研究历史记录。在本文中,我们介绍了\ emph {正常的在线分配问题},该变体包括用于总资源消耗的非线性规范器。在此问题中,请求多次到达,对于每个请求,决策者需要采取生成奖励和消耗资源的操作。目的是同时最大化可分离可分离的奖励和受资源限制的不可分级规范器的值。我们的主要动机是允许决策者履行可分离目标,例如与辅助,不可分配的目标的经济效率,例如分配的公平或公平。我们设计了一种简单,快速,并且具有随机I.I.D的良好性能的算法。〜和对抗的投入。特别是,我们的算法在随机I.I.D下渐近最佳。输入模型并达到固定的竞争比率,当输入是对越野的时,取决于常规管道。此外,算法和分析不需要贡献函数和消耗函数的凸起或凹面,这允许更多的模型灵活性。数值实验证实了算法在互联网广告应用中的算法和正则化的有效性。
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 谷歌翻译
在这项工作中,我们研究了数据驱动的决策,并偏离了经典的相同和独立分布(I.I.D.)假设。我们提出了一个新的框架,其中我们将历史样本从未知和不同的分布中产生,我们将其配置为异质环境。假定这些分布位于具有已知半径的异质球中,并围绕(也是)未知的未来(样本外)分布,将评估决策的表现。我们量化了中央数据驱动的策略(例如样本平均近似值,也可以通过速率优势)来量化的渐近性最坏案例遗憾,这是异质性球半径的函数。我们的工作表明,在问题类别和异质性概念的不同组合中,可实现的性能类型的变化很大。我们通过比较广泛研究的数据驱动问题(例如定价,滑雪租赁和新闻顾问)的异质版本来证明框架的多功能性。在途中,我们在数据驱动的决策和分配强大的优化之间建立了新的联系。
translated by 谷歌翻译
我们通过反馈信息研究了离线和在线上下文优化的问题,而不是观察损失,我们会在事后观察到最佳的动作,而是对目标功能充分了解的甲骨文。我们的目标是最大程度地减少遗憾,这被定义为我们的损失与全知的甲骨所产生的损失之间的区别。在离线设置中,决策者可以从过去段中获得信息,并且需要做出一个决策,而在在线环境中,决策者在每个时期内都会动态地基于一组新的可行动作和上下文功能,以动态进行决策。 。对于离线设置,我们表征了最佳的最小策略,确定可以实现的性能,这是数据引起的信息的基础几何形状的函数。在在线环境中,我们利用这种几何表征来优化累积遗憾。我们开发了一种算法,该算法在时间范围内产生了对数的第一个遗憾。
translated by 谷歌翻译
我们研究一种在线线性编程(OLP)问题,该问题通过随机输入最大化目标函数。当随机输入遵循一些I.I.D分布时,对分析此类OLP的各种算法的性能进行了充分的研究。要问的两个核心问题是:(i)算法如果随机输入不是I.I.D而是静止的,并且(ii)如果我们知道随机输入是潮流的,那么我们如何修改我们的算法,因此,该算法可以达到相同的效率。固定。我们通过分析再生类型的输入类型来回答第一个问题,并表明两种流行算法的遗憾与其I.I.D对应物相同的顺序界定。我们讨论了线性增长的输入的背景下的第二个问题,并提出了两种趋势自适应算法。我们提供数值仿真,以说明在再生和时尚输入下算法的性能。
translated by 谷歌翻译
以下序列出售了许多产品:首先显示焦点产品,如果购买客户,则显示一种或多种辅助产品以供购买。一个突出的例子是出售航空票,首先显示航班,并在选择时出售了许多辅助机构,例如机舱或袋装选项,座位选择,保险等。该公司必须决定销售格式 - 是按串联捆绑或作为捆绑销售的形式出售 - 以及如何分别或捆绑产品为焦点和辅助产品定价。由于仅在购买焦点产品后才考虑辅助性,因此公司选择的销售策略会在产品之间创建信息和学习依赖性:例如,仅提供一套捆绑包将排除学习客户对焦点的估值和辅助产品。在本文中,我们在以下情况下研究了这种焦点和辅助项目组合的学习策略:(a)纯捆绑向所有客户捆绑,(b)个性化机制,在其中,根据客户的某些观察到的功能,这两种产品都会呈现并以捆绑包或顺序定价,(c)最初(适用于所有客户),并在地平线期间永久切换(如果更有利可图)。我们为所有三种情况设计定价和决策算法,遗憾的是由$ o(d \ sqrt {t} \ log t)$限制,以及第三种情况的最佳切换时间。
translated by 谷歌翻译
我们考虑带有背包的土匪(从此以后,BWK),这是一种在供应/预算限制下的多臂土匪的通用模型。特别是,强盗算法需要解决一个众所周知的背包问题:找到最佳的物品包装到有限尺寸的背包中。 BWK问题是众多激励示例的普遍概括,范围从动态定价到重复拍卖,再到动态AD分配,再到网络路由和调度。尽管BWK的先前工作集中在随机版本上,但我们开创了可以在对手身上选择结果的另一个极端。与随机版本和“经典”对抗土匪相比,这是一个更加困难的问题,因为遗憾的最小化不再可行。相反,目的是最大程度地减少竞争比率:基准奖励与算法奖励的比率。我们设计了一种具有竞争比O(log t)的算法,相对于动作的最佳固定分布,其中T是时间范围;我们还证明了一个匹配的下限。关键的概念贡献是对问题的随机版本的新观点。我们为随机版本提出了一种新的算法,该算法是基于重复游戏中遗憾最小化的框架,并且与先前的工作相比,它具有更简单的分析。然后,我们为对抗版本分析此算法,并将其用作求解后者的子例程。
translated by 谷歌翻译
除了最大化总收入外,许多行业的决策者还希望保证跨不同资源的公平消费,并避免饱和某些资源。在这些实际需求的推动下,本文研究了基于价格的网络收入管理问题,需求学习和公平性关注不同资源的消费。我们介绍了正式的收入,即以公平的正规化为目标,作为我们的目标,将公平性纳入收入最大化目标。我们提出了一种原始的偶型在线政策,并使用受到信心限制(UCB)的需求学习方法最大化正规化收入。我们采用了几种创新技术,以使我们的算法成为连续价格集和广泛的公平规则化的统一和计算高效的框架。我们的算法实现了$ \ tilde o(n^{5/2} \ sqrt {t})$的最坏遗憾,其中$ n $表示产品数,$ t $表示时间段。一些NRM示例中的数值实验证明了我们算法在平衡收入和公平性方面的有效性。
translated by 谷歌翻译
带背包(BWK)的匪徒是供应/预算约束下的多武装匪徒的一般模型。虽然BWK的最坏情况遗憾的遗憾是良好的理解,但我们提出了三种结果,超出了最坏情况的观点。首先,我们提供上下界限,其数量为对数,实例相关的后悔率的完整表征。其次,我们考虑BWK中的“简单遗憾”,在给定回合追踪算法的性能,并证明它在除了几轮之外的一切。第三,我们提供从BWK到匪徒的一般“减少”,这利用了一些已知的有用结构,并将这种减少应用于组合半刺点,线性上下文匪徒和多项式登录匪徒。我们的成果从\ CiteT {AgraWaldevanur-EC14}的BWK算法构建,提供了新的分析。
translated by 谷歌翻译
We study distributionally robust optimization (DRO) with Sinkhorn distance -- a variant of Wasserstein distance based on entropic regularization. We provide convex programming dual reformulation for a general nominal distribution. Compared with Wasserstein DRO, it is computationally tractable for a larger class of loss functions, and its worst-case distribution is more reasonable. We propose an efficient first-order algorithm with bisection search to solve the dual reformulation. We demonstrate that our proposed algorithm finds $\delta$-optimal solution of the new DRO formulation with computation cost $\tilde{O}(\delta^{-3})$ and memory cost $\tilde{O}(\delta^{-2})$, and the computation cost further improves to $\tilde{O}(\delta^{-2})$ when the loss function is smooth. Finally, we provide various numerical examples using both synthetic and real data to demonstrate its competitive performance and light computational speed.
translated by 谷歌翻译
节流是当今在线广告市场中最受欢迎的预算控制方法之一。当一个受预算受限的广告商雇用节流功能时,她可以在广告平台建议出价后选择是否参加拍卖。本文重点介绍了从理论观点重复的第二价格拍卖中的动态预算节流过程。潜在问题的一个重要特征是,广告商不知道进入市场时竞争最高的出价。为了模拟消除这种不确定性的困难,我们考虑了两种不同的信息结构。广告商可以通过全信息反馈获得每轮竞争最高的投标。同时,通过部分信息反馈,广告商只能在她参加的拍卖中获得最高竞争的出价。我们提出了OGD-CB算法,该算法涉及在线广告查询面临的同时分配学习和收入优化。在这两种情况下,我们都证明该算法保证了$ O(\ sqrt {t \ log t})$遗憾,概率$ 1- o(1/t)$相对于流体自适应节流基准。通过证明$ \ omega(\ sqrt {t})$的下限在最小的后悔中,即使是最佳的最佳选择,我们就建立了算法的近乎最佳性。最后,我们将节流的最佳流体最佳与起搏相提并论,这是另一种广泛采用的预算控制方法。这些基准的数值关系使我们对不同的在线算法进行预算管理的比较有了进一步的见解。
translated by 谷歌翻译