最优实时报价策略

我们应该规定支出不得超过，但出于技术原因，我们更愿意考虑一个宽松的问题，并惩罚额外支出。因此，我们考虑以下标准的最大化：EhIT- K min（ST，0）i，其中K衡量额外支出惩罚的重要性。出于数学原因，我们更愿意把随机最优控制问题写成最小化问题：inf（bt）t∈啊-IT+K min（ST，0）i，其中A是具有R值的可预测过程集+∪ {+∞}.该模型可以很容易（稍微）修改，以涵盖截断函数f的情况，即f等于给定价格水平以上的0。这个过程定义得很好，因为N∈ N*, pn∈ L(Ohm).特别是，我们将考虑极限情况K→ +∞ 作为一种观察当最高总开支被强加时会发生什么的方法。价值函数：为了解决这个随机最优控制模型，我们引入了价值函数u:（t，I，S）∈ [0，T]×N×N(-∞,\'S]7→ inf（bs）s≥T∈吃了-Ib，t，IT+K minSb，t，ST，0,其中Atis是[t，t]上的一组可预测过程，其值为R+∪ {+∞}, 和DSB，t，Ss=-pNs{bs>pNs}dNs，Sb，t，St=S，dIb，t，Is=1{bs>pNs}dNs，Ib，t，It=I.2.2随机最优控制问题的解2。2.1非标准HJB方程的表征为了解决上述随机最优控制问题，我们引入了相关的HamiltonJacobi-Bellman（HJB）方程，该方程对应于从动态规划原理在离散时间推导的Bellman方程（A.2）的连续时间等价物——见附录。这里的HJB方程是：- 图（t，I，S）- λinfb∈R+Zbf（p）（u（t，I+1，S）- p）- u（t，I，S））dp=0，（2.2）终端条件u（t，I，S）=-I+K min（S，0）。式（2.2）是一个非标准的积分微分HJB方程，类似于式。

（A.2）。因为目标函数是变量I中的一个函数，所以可以通过考虑ansatz u（t，I，S）=-I+v（t，S）。有了这个安萨兹，等式（2.2）实际上变成：- 电视（t，S）- λinfb∈R+Zbf（p）（v（t，S）- p）- v（t，S）- 1） dp=0，（2.3），终端条件v（T，S）=K min（S，0）。为了避免本文过于技术化，我们将重点放在应用上，而不是对我们推导的积分微分贝尔曼方程进行数学分析。感兴趣的读者可以通过使用[5]中介绍的高级粘度技术，得出存在性和唯一性结果。值得注意的是，我们将通过流体极限来近似这个问题，经典的弱半凹解方法适用于这个问题——参见[6,8]。等价地，等式（2.3）可以写成-电视（t，S）- λinfb∈R+-F（b）+Zbf（p）（v（t，S）- p）- v（t，S））dp= 0.Eq.（2.3）是另一个非标准积分微分Hamilton-Jacobi-Bellman，但只有一个空间维度，而不是两个。很容易验证它是否对应于以下随机最优控制问题：inf（bt）t∈AE-λZTF（bt）dt+K min（ST，0）, （2.4）其中A是一组可预测的过程，其值以R为单位+∪ {+∞}.变量u（t，I，S）的变化-I+v（t，S）是降低问题维数的关键。为了理解基本原理，让我们注意到-u（t，I，S）是（直到惩罚条款）广告交易者在时间间隔[0，t]内预期购买的印象数量，如果在时间t，他已经购买了相当于I的印象数量，并且在[t，t]上有一个S的最佳花费金额。

因为在[t，t]期间购买的印模数量并不取决于已经购买的印模数量，除非通过已经花费的预算——或者，相当于，尚未花费的预算——购买的印模数量-u（t，I，S）- 我应该独立于I.H.encethe ansatz u（t，I，S）=-I+v（t，S）。特别是数量-v（t，S）表示（直到惩罚期限）广告交易者在时间间隔[t，t]内预期购买的印象数量，如果他在时间t有一个S在[t，t]上的最佳花费。2.2.2我们需要超出等式（2.3）的原因从前面的段落中，可以认为问题几乎完全解决了。由于式（2.3）描述了最优投标策略，在系统的每个状态（t，S）中找到最优投标实际上可以归结为执行一个反向（单调）数值格式来近似式（2.3）的解。然而，值得注意的是，广告交易者面临的问题有两个层面：宏观层面是战术层面。这个尺度与时间范围和广告交易员在时间间隔内必须花费的现金量有关[0，T]。实际上，对于盘中战术，数量级在10到10之间- T为10秒（秒），在E10范围内- 10对于S.o微观尺度是每次拍卖的尺度，与强度λ以及变量b和p（在等式（2.3）的积分项中）有关。这些变量的数量级约为10秒-1对于λ，在范围e10内-5.- 10-2每次投标。如果想要在（t，S）中的网格上近似求解等式（2.3），时间步长t和现金/空间步骤S应与微观尺度兼容。

如果我们认为广告活动构成了宏观规模，那么采用这种规模可能会被视为中观的。乍一看，这些值似乎很小。我们提醒读者，行业标准是衡量1000次印象（CPM，或每千次成本）的投标水平和价格。例如，对于给定的拍卖，如果一个从业者谈论出价为e1，那么实际上就是e10-3.考虑到拍卖请求的快速到达，自然时间步长是10点左右-4秒。就花费的现金而言，如果想要精确计算每次拍卖的最佳出价，那么S大约在E10左右-7，考虑到之前讨论的投标数量级。考虑到宏观尺度上考虑的数量级，我们需要考虑一个网格上的数值格式，该网格具有10- 10点时间和10点- 在太空中10点，这在计算上非常昂贵。尽管可以建立智能数值方法来避免网格中每个点的计算，但问题的多尺度性质在实践中是一个重要问题。避免使用计算机密集型数值方法的一种方法是寻找近似形式。正如我们将在下面展示的，这种近似可以通过在等式（2.3）的积分项中使用一阶泰勒展开来找到。2.3几乎封闭形式的近似解在本小节中，我们的目标是近似值函数v和由此产生的最优控制函数（t，S）7→ B*（t，S）对应于最优投标策略——后者的特征是V（t，St-- B*（t，圣-)) = v（t，圣-) + 1，（2.5）如果该方程有解，或通过b*（t，圣-) = +∞ 否则，即。

如果我们在limS的案子里→-∞v（t，S）≤ v（t，圣-) + 1.我们在以下段落中获得的近似值的主要思想是替换术语v（t，S）-p）-式（2.3）中v（t，S）的一阶泰勒展开式-PSv（t，S）。因此，我们将等式（2.3）替换为：- 电视（t，S）- λinfb∈R+-Zbf（p）（1+p）Sv（t，S））dp=0。（2.6）终端条件v（T，S）=K min（S，0）。直观地说，由于问题的多尺度性质，该近似值是相关的：b的值范围应比S.2.3.1 A流体极限近似值在以下段落中的值小几个数量级，我们证明，公式（2.6）是与变分问题相关的H amilton-Jacobi方程，该变分问题可以被视为随机变量的流体极限，而不是公式（2.3）的数值解需要更多时间（秒、分钟等）的问题比授权向拍卖服务器发送出价的最长时间（毫秒）计算。实际上，该解决方案可以提前计算，然后嵌入内存中的查找表中，从而允许低延迟请求。在在线估计参数的情况下，这个问题更为关键——见[12]。下面将讨论这一点。我们在上一小节中考虑的最优控制问题。为此，让我们介绍以下优化问题：inf（~bt）t∈阿德特-λZTF（~bt）dt+K min~S~bT，0,式中yenSyenbt=-λG（~bt）dt，G:x∈ R+∪ {+∞} 7.→Zxpf（p）dp，其中Adetis是一组F-可测过程，其值为R+∪ {+∞}.与该问题相关的值函数＠v定义为：＠v（t，S）=inf（＠bs）S≥T∈阿德特-λZTtF（~bs）ds+K min~S~b，t，ST，0,式中dSb，t，Ss=-λG（~bs）ds，~S ~b，t，St=S。我们有以下定理：定理2.1。

让我们定义（x）=λsupb∈R+Zbf（p）（1+xp）dp=(-λxR-xF（p）dp，x<0λ1+xR∞pf（p）dp, 十、≥ 0.值函数v由以下公式给出：~v（t，S）=supx≤0Sx- （T）- t） H（x）-x4K.这是Hamilton-Jacobi方程（2.6）的唯一弱半凹解。此外，最优控制函数（t，S）7→~b*（t，S）由以下公式给出：o如果S≥ λ（T）- t） R∞pf（p）dp，然后b*（t，S）=+∞.o 如果S<λ（T）- t） R∞pf（p）dp，然后b*（t，S）=-十、*, w在这里x*其特征是s=（T- t） H′（x）*) +十、*2K。（2.7）证据。通过使用变量的变化as=λG（~bs）∈ I=[0，λR∞pf（p）dp]，我们有：~v（t，S）=inf（as）S≥T∈A′detZTtL（as）ds+K minbSa，t，ST，0, （2.8）其中A′det是一组F-可测过程，其值在I中，其中dbsa，t，Ss=-asds、bSa、t、St=S，其中函数L定义为：L:a∈ I 7→ -λFG-1.λ.L在I的内部是连续可微的，带有：L′（a）=G-1.′λF′G-1.λ= -FG-1.λG′G-1.λ= -G-1.λ.特别是，因为G是一个递增函数，所以L′是递增的，因此，L是严格凸的。现在让我们计算L:L的勒让德-芬切尔变换*（x） =苏帕∈伊克萨- L（a）=supb∈R+λxG（b）+λF（b）=λsupb∈R+Zb（1+xp）f（p）dp（2.9）=H（x）。如果x<0，则与等式（2.9）中的上确界相关的一阶条件为f（b*) （1+b）*x） =0。换句话说：x<0=> B*= -x、 如果x是非负的，那么b*= +∞.在前一种情况下，我们可以写（通过使用部分积分）：H（x）=λsupb∈R+Zb（1+xp）f（p）dp=λZb*f（p）（1+xp）dp=-λxZ-xF（p）dp。因此L的Legendre-Fenchel变换是H，可以写成：H（x）=(-λxR-xF（p）dp，x<0λ1+xR∞pf（p）dp, 十、≥ 0.很容易检查H是一个两次连续可微凸函数。我们知道，从经典变分演算中，~v由Hopf-Lax公式给出：~v（t，S）=infy∈[S]-λR∞pf（p）dp（T）-t） ，S]（T）- t） Ls- yT- T+ K min（y，0）.

（2.10）通过使用非理想卷积，我们可以将等式（2.10）转换为：~v（t，S）=supxSx- （T）- t） H（x）- supyyx- K min（y，0）= 好的Sx- （T）- t） H（x）- χR-（十）-x4K= 好的≤0Sx- （T）- t） H（x）-x4K. （2.11）这是该定理的第一个结果。此外，我们知道它是以下Hamilton-Jacobi方程的唯一弱半凹解：-t~v（t，S）+H(当终端条件为最小值K时，Sv（t，S））=0。这个等式与等式（2.6）完全相同，因此是定理的第二个断言。此外，修正问题（2.8）中的最优控制由A给出*（t，S）=H′(v（t，S））。简单的计算给出：H′（x）=（λR-xpf（p）dp=λG-十、, x<0λR∞pf（p）dp，x≥ 特别地，H′（0）=λR∞pf（p）dp。因为跛行→+∞pf（p）=0，函数H′与：H′（x）连续可微=(-λxf-十、, x<00，x≥ 因此，初始问题中的最优控制函数为：~b*（t，S）=(-Sv（t，S），v（t，S）<0+∞, S~v（t，S）≥ 0.如果是≥ （T）- t） H′（0）=λ（t）- t） R∞pf（p）dp，则等式（2.11）中的最大值达到atx*= 0.因此，S~v（t，S）=0和~b*（t，S）=+∞.否则，等式（2.11）中的最大值在x处达到*≤ 0的唯一特征为：S=（T- t） H′（x）*) +十、*2K。特别地，v（t，S）=x*和b*（t，S）=-十、*x在哪里*其特征是等式（2.7）。2.3.2最优投标策略的近似值及其解释定理2.1要求使用v作为v的近似值。然后，最优投标策略（b*t） t可近似为b*（t，圣-), 或者通过求解等式（2.5），其中v被v代替。在下面的内容中，我们考虑前一种方法。此外，我们考虑了K→ +∞.

随后，我们近似得出最优报价b*时间t乘以b*∞（t，圣-), 函数b*∞定义为：o如果≥ λ（T）- t） R∞pf（p）dp，然后b*∞（t，S）=+∞.o 如果S<λ（T）- t） R∞pf（p）dp，然后b*∞（t，S）由以下公式得出：~b*∞（t，S）=-H′-1.装货单-T.为了理解上述结果，值得回顾一下∞pf（p）dp是要击败的平均价格，λ（T）- t） 是在时间t和终端时间t之间，广告交易者将参与的预期拍卖次数。因此，λ（T）- t） R∞pf（p）dp是广告交易者为了赢得所有他收到请求的拍卖而出价的预期现金金额。因此，在我们的风险中性设定中，出价b是很自然的*∞（t，圣-) = +∞ 在时间t，如果剩余的花费金额-大于λ（T）- t） R∞pf（p）dp。如果圣-< λ（T）- t） R∞pf（p）dp，然后是近似值b*∞（t，圣-) 最优报价b*tveri fies：考虑到b值非常大，似乎与流体极限近似值相反。然而，事实并非如此，因为与预算S相比，每一次赢得的拍卖最终支付的价格仍然非常小，除非可能接近最终时间T。λ（T）- t） Z~b*∞（t，圣-)pf（p）dp=St-.为了理解这种投标策略，让我们考虑一下从时间t开始的情况，在有趣的情况下，即当-< λ（T）- t） R∞pf（p）dp。如果我们使用上述最优投标策略的近似值，剩余现金的动态为（0≤ T≤ s≤ T）：dSs=-pNs{b*∞（s，Ss）-)>pNs}dNs，St=S。因此：dE[Ss]=-E“λZb*∞（s，Ss）-)pf（p）dp#ds=-E[Ss]T- sds。这就给出了E[Ss]=ST-sT公司-T

换句话说，最优投标策略的近似值是这样的：平均而言，剩余的现金在[t，t]上平均花费。前面分析的一个主要结果是，最优性不仅体现在最优出价上，还体现在预算支出的速度上。后者在实施方面很有帮助。事实上，通过优化曲线（也称为预算调整，见[10]）定义解决方案，可以通过跟踪目标曲线的反馈控制系统动态控制投标，而不依赖于函数f的形式。从这个角度来看，对最优投标函数的确切了解就不再必要了。然而，该分析基于流体近似。随后，只要拍卖请求的数量足够大，它就有效。对于关注库存小部分的受众策略（例如，仅针对少数客户、将策略限制为优质库存、为非常特定的横幅格式购买慢货等），需要初始随机控制问题解决方案的数值近似值。2.4数值示例我们给出一个数值示例f或一个在100秒内花费e1的算法。由于该算法的高频率特性，考虑到更大的时间框架和更大的预算，从数学角度来看并不会产生重大差异。注意，支出率(~ 考虑到我们的问题，e 500/天——尽管考虑到整体广告预算的规模，它可能很小——是现实的：我们正专注于一种算法，该算法已经局限于特定的频道、观众和库存子集。

实际上，广告交易台通过一系列算法（如本文所示）动态分配一天的总预算。在拍卖请求到达率随时间变化λt的情况下，一个类似的变分问题solvedin[10]表明，最优策略是按λt的比例支出。在这种情况下，网格的大小可以减小，因为λ很小。多个投标算法之间的总体预算优化分配超出了这项工作的范围。然而，我们可以将第3节的扩展视为解决这个问题的一种方式。自然的。4.1 v和b的数值近似*在我们的数值实验中，我们假设要拍的价格分布是参数为u的指数分布，即f（p）=ue-up。我们选择u=2·10e-1，这与e0.5级的CPM一致。我们在图1中表示HJB方程（2.3）解v的数值近似值。如上所述，数量-v（t，S）可以被解释为（直到惩罚时间），当t时的剩余预算为S.S（剩余现金）0.00.20.40.60.81.0t（时间）0204060100-v（t，S）020000400060008000010001200016000018000图1：HJB方程（2.3）的解时，analgorithm按照最佳策略从t时购买的预期印模数。λ=500秒-1，T=100s和‘s=e1。在求解HJB方程（2.3）时，最重要的计算量是最优控制，即最优投标函数（t，S）7→ B*（t，S）。该函数如图2所示。