论文名称：Bid Optimization by Multivariable Control in Display Advertising
1.摘要
实时竞价(RTB)是展示广告的一个重要领域，广告主利用需求方平台(DSPs)提供的扩展信息和算法来提升广告效果。DSP的一个常见功能是在预算约束下帮助广告主获得尽可能多的广告价值。在实践中，广告主通常会添加某些关键指标约束，广告活动必须满足这些约束。本文主要研究广告主以最大化转化率为目标、并将每次点击成本(CPC)作为约束条件的普遍情况。我们将这类问题转化为一个线性规划问题，并利用对偶方法推导出最优报价策略。针对适用性问题，提出了一种基于反馈控制的解决方案，并设计了多变量控制系统。我们在淘宝网的实际数据上做了实验，与行业内的先进实践方法相比，实验结果证明了方案的有效性和优势
2.出价策略
在本节内容中，我们首先回顾一下RTB生态系统的主要知识，然后定义竞价优化问题，最后推导出最优竞价策略，并讨论竞价策略的特点
2.1 RTB生态系统
为了能够让文章形成闭环，我们简单介绍一下RTB生态系统及其相关技术。RTB的工作流如下图所示：
1）用户访问一个支持在线广告的网站，网站将会发送一个广告请求到广告交易平台
2）广告交易平台发起拍卖并请求来自DSP的出价
3）DSP代表广告主将竞价出价和广告一起提交给广告交易平台
4）广告交易平台进行广告拍卖，并向获胜的DSP收取广告费用
5）获胜DSP的广告将会在该网站展示
6）用户反馈信息随后会发送给相应DSP
为了避免冗余，我们将重点放在与我们的工作密切相关的步骤3)、4)和6)上
当DSP收到来自广告交易平台的竞价请求时，它会根据自己的竞价策略计算出广告主的竞价价格。因为转化率是大多数广告主的关注目标，几乎所有的竞价策略都严重依赖于学习模型来预估广告点击率和转化率。此外，一些DSP也可能基于获胜价格的预测来制定竞价策略。CTR/CVR预估和竞价空间预估本身是研究较多的领域，超出了我们的研究范围。因此，我们假设预估问题已经被很好地解决，点击和转换的期望概率可以分别用CTR和CVR来量化
当一个DSP赢得了在拍卖中展示广告的机会，广告交易平台就会对它收费。在行业内广泛采用的广义第二价格(GSP)拍卖急之下，收费价格等于第二最高竞价。还有其它一些拍卖机制，如VCG拍卖机制。本文在不是一般性的前提下，基于最常见的GSP机制进行讨论
用户对广告的任何反馈，比如点击量和转化率，都会被发送给相应的DSP。DSP可以利用这些反馈来训练预测模型，并及时调整其竞价策略。此外，DSP将对这些反馈进行整合，并将其反馈给广告主。在我们提出的系统中，可以利用这些反馈在广告活动的整个生命周期中不断调整竞价策略
2.2 问题定义
假设一天内有个广告展示机会，我们按照这些广告机会产生的顺序对其标记为。对于广告主来说，每个广告展示机会有不同的价值，我们用表示的价值。基于，我们可以计算出提交给广告交易平台的竞价出价。每个广告展示机会有一个赢价，它的含义是广告主如果想要赢得该次广告展示机会，在GSP机制下的消耗。用表示是否在上展示广告，它的值是0或者1。基于以上概念，广告活动的价值和消耗可用等式1）和等式2）表示：
我们用公式(3)定义CPC。需要注意的是，我们使用CTR代替真正的点击，这可以让我们更加方便地表述这个问题。这样的替换在很大程度上有利于我们的理论分析，而且在后续的实际系统设计中影响比较小
其中，质量可用来表示。我们可将上述问题表述为一个线性规划问题：
2.3 最优竞价策略
LP1是一个线性规划问题，它是在线性约束下寻找最优使得目标函数取得最大值。已经有很多直接解决此类问题的算法，然而，我们的目的是推导最优的竞价策略而不是分配策略。换句话说，我们不需要关心的真实值，我们关心的是竞价策略如何影响。考虑到这一点，我们创造性地使用了对偶理论。每个线性规划问题，都可以看作是一个原问题，能够被转化为一个对偶问题。根据对偶定理，通过相应的对偶解可以得到最优原解。这些数学理论给了我们启示，我们将原空间和对偶空间结合起来，推导出以下定理：
THEOREM 2.1. The optimal bidding strategy formulation is:
最优竞价策略如公式(6)所示，其中和是超参数，和对偶问题的最优解相对应。本文的后续章节会研究和的性质，现在，我们先来证明Thm 2.1
将LP1转化为对偶问题：
假设原问题(LP1)的最优解是，对偶问题(LP2)的最优解是。根据互补松弛条件，可以得到：
我们直接设置出价如下：
然后，我们可以将上面的等式(8)转化为下面的等式(10)：
1）根据等式(10)，如果广告活动赢得了展示机会，那么，。同时，，因此，
2）如果广告活动没有获得展示机会，可以从等式(9)中直接推导出。然后，从不等式(7)中可以推导出，这意味着
总得来说，对于任意一次展示机会，竞价策略需要保证是最优的，这会使得问题LP1有最优解。这就是说，当最优(广告活动赢得展示机会)，最优竞价策略的竞价出价应该高于，这会保证广告活动赢得展示机会。因此，广告活动只需要根据等式(6)来调整出价，就会在约束条件下最大化广告价值
值得注意的是，等式(6)并没有明确告知和的值。实际上，通过线性规划算法来求解对偶问题很容易推导出最优的和。这样的工作对理解我们的方案并没有太大的帮助，因此我们在这里不讨论如何计算和的值
我们使用式(11)和式(12)以及图(2)来重新定义最优竞价策略LP1，其中是单次点击的竞价出价。当一个广告展示机会到来时，首先要确定这个点击的竞价出价。最终的出价是将竞价出价和点击率相乘得到，这部分计算可以在系统中自动完成。此外，在GSP拍卖机制下，一次点击的成本是不会高于一次点击的出价的，所以是与CPC直接相关联的。因此，为了简化我们的证明，我们着重讨论竞价出价
我们开始讨论最优竞价策略，如图2.a所示，有一些明显的现象。第一，点击出价与呈现明显正相关的。我们应该为更有价值的点击提供更高的出价，而为不那么有价值的点击提供相对较低的出价；第二，竞价出价与呈现线性关系。这是一个很自然的结果，因为我们最大化的目标函数是关于的线性函数；第三，竞价策略会像图中所示那样在两点处交叉，本文的后续分析将会详细讨论这个现象。然而，有一个不同寻常的事实：函数图像不一定通过原点。具体地说，即使广告展示机会对广告主来说没有价值，竞价价格也将不会是零。我们为一个毫无价值的广告展示机会提供一个非零的竞价价格似乎有点不合常理。我们认为主要理由是：在考虑CPC约束的情况下，竞价策略试图赢得一些即使没有任何价值的广告展示机会，以降低整体CPC，从而可以赢得一些有价值但CPC较高的广告展示机会
3.系统设计
本节我们将会讨论竞价策略在实际场景的应用性问题，并提出了基于反馈控制的解决方案。在最优竞价策略超参数的分析基础上，提出了多变量控制系统
3.1 应用问题
如问题LP2所述，为了求解线性规划问题，并获得最优竞价策略，我们需要知道当天每个广告展示机会的信息，包括赢价、CTR和CVR。然而，这些信息在现实世界中只有在当天结束时才能获得，而最优投标策略则需要在活动开始前确定。除了很难在拍卖开始之前预估所有这些广告的曝光率之外，由于电子商务的动态性，如何预测当天的广告展示机会本身仍然是一个开放性的问题。有人可能会说，有很多统计方法可以解决这个问题：最优解决方案可以从足够的历史数据中得到，并在未来应用。这种算法的基础假设是：变量的分布是平稳的。然而，在动态RTB环境中，不仅仅是广告机会的分配，还有其它因素，如获胜价格、CTR和CVR都不是固定不变的。因此，基于历史数据推导出的最优竞价策略对未来将不再是最优的，甚至有可能打破CPC约束条件
3.2 基于反馈控制的解决方案
正如上一节所讨论的，由于竞价环境的动态性，基于历史数据得到的最优竞价策略是不可靠的。因此，我们需要利用实时信息来调整竞价策略。反馈控制是一种从反馈和外界噪声中处理动态系统的控制方法，由于其鲁棒性和有效性，在工业中得到了广泛的应用。反馈控制系统根据系统输出的反馈来调整系统输入，以达到理想的效果。在我们的场景中，我们可以自然地将竞价策略和RTB环境集成为一个动态系统，并将竞价策略p和q的超参数作为系统的输入。这样，问题就变成了一个反馈控制问题。仍然存在一个问题：什么是理想的效果？以及我们应该关注输出的什么反馈？首先，我们的目标是最大化广告价值以及控制CPC；其次，为了是广告价值最大化，我们应该平滑预算支出，以在分散的时间上赢得有价值的广告展示机会。因此，我们需要控制预算支出，同时控制CPC。我们提出的反馈解决方案如下:为了提高广告效果，我们根据广告的实时反馈来调整预算支出，控制CPC
我们简要介绍一下标准的反馈控制系统。反馈控制系统的整体框架如图3所示。输出的理想值也叫做参考值，它是根据特定任务预先设置的。传感器从系统输出中测量出变量的实际值，并将其传输给控制器。将测量值与参考值进行比较，控制器通过其预先设定的算法或策略来调整系统的输入，以减小两者之间的差异。PID是工业中应用最广泛的反馈控制器，众所周知的是，在不了解底层原理的情况下，PID控制器可以提供最好的效果。PID控制器在每一个时间步长t处不断计算实测值与参考值之间的误差，并根据的比例、积分、导数项组合产生控制信号。随后，执行器模型将会利用控制信号来调整系统输入。在网络广告场景中，使用离散步长是一种常见和实用的方法，因此，PID过程可以表述为如下方程，其中和是PID控制器的权重参数：
3.3 超参数控制
我们将问题转化为一个反馈控制系统，并在上一节确定了动态系统(竞价策略和RTB)、输入参数(和)和输出变量(预算支出和CPC)。这里的挑战是如何在控制预算支出和CPC的同时调节和。由于有多个输入参数和多个输出变量，我们不能在我们的场景中直接应用PID控制器，因为这种控制器是为单一输入参数和单一输出变量的系统设计的。有一些多变量控制方法，如模型预测控制，我们将在下一节中的设计中利用它们的基本思想。在本节中，我们将重新讨论等式(11)所表述的最优竞价策略，并分享我们设计多变量控制系统的想法
我们分析了超参数和对最优竞价策略的影响。需要明确的一点是，和分别是约束不等式(4)和(5)的对偶变量，我们探究了它们和约束的关系
图(4)给出了在固定，分别在减小、增大、等于0和等于时的最优竞价策略。值得注意的是，竞价出价会影响期望消耗：竞拍出价越高，成本也会越高，竞拍也可以赢得更多的广告展示机会。如图(4)所示，竞价出价一般会随着p的增加或减少而降低或提高。当增加时，竞价出价会围绕点顺时针旋转。由此产生的现象是：高于零的竞价出价将会降低，低于零的竞价出价将会提高，从而期望成本将会降低。取和作为极端例子，当且竞价出价持续为零时，广告活动将永远不会被收费。当时，预算将不再是约束。由于仍然存在CPC约束，竞价价格不会无限高，竞价策略的斜率完全由控制。如果我们同时将也设为0，这意味着CPC约束也取消了，竞价价格将无限高，活动将赢得所有广告展示机会。根据图中所示，我们认为对预算支出有直接有效的控制能力，可以明显降低预算支出的速度
以相同的方式，我们固定，并设置分别减小、增大、等于0和等于。如图(5)所示，在最优竞价策略上的影响明显不同于。当我们增加或减少时，最优竞价策略会沿着顺时针或逆时针旋转。以增加为例，高于的出价将降低，低于的出价将提高。这样一来，CPC低于C的广告机会就会更多，CPC高于C的广告机会就会更少。综合结果是，CPC更有可能低于C。极端情况下，当时，CPC一定会低于C。当时，CPC约束将会不存在，竞价策略由决定，并退化为最优预算约束竞价策略。经过以上分析，我们认为完全可以由来控制。综上，我们得到了以下两个结论：
1）超参数对预算支出速度有直接有效的控制力。在给定值的情况下，可以通过来降低预算支出速度
2）超参数对CPC有直接有效的控制力。在给定值的情况下，可以通过来调整CPC
3.4 多变量控制
正如我们上一节所述，预算支出速度和CPC可以明确地由和来控制。换句话说，和可以分别用来控制预算支出和CPC，彼此视为外部噪声。因此，我们可以将多变量反馈控制问题分解为两个单变量反馈控制问题。这样的话，PID控制器可以很容易地部署，如图(6)所示，我们提出了独立的PID设计，用和来区分这两个控制器
为了进一步进行分析，我们重新回顾3.3节中的分析。如图(4)所示，增加一般会降低竞价价格，进而降低预算支出速度。增加引起的另外一个效应是，期望CPC也会降低。根据这些观察，调整实际上会对CPC产生影响。同样，调整也会对预算支出产生影响。虽然我们设计的独立PID控制系统可以处理这种耦合效应，此时这种耦合效应被当做外部噪声处理，但通过解决这类问题可以进一步提高系统的性能。然而，由于我们对动态系统没有明确的了解，这种耦合效应很难量化和补偿。为了解决这类问题，我们利用模型预测控制(MPC)的基本思想来预测和补偿耦合效应。需要注意的是，我们没有直接在我们的控制系统中应用MPC，因为对高度非线性的RTB环境建模代价非常大，是不切实际的
在我们的设计中，与人的经验相结合，模型预测模块只需要预测耦合效应，一般情况下用线性模型就可以了。如图(7)所示，在PID控制器之后设置模型预测模块，通过解决耦合效应来调节控制信号
MPC的一个重要组成部分是一个描述动态系统行为的模型。在我们的方案中，我们根据成本和CPC对竞价环境进行建模。如式(16)所示，其中是一个的矩阵，是一个的矩阵。在我们从反馈中获得和后，我们可以通过等式(17)来调整和，可以推导出结果如式(18)所示。由式(18)中公式可知，和的控制信号应该是成本和CPC变化的线性组合。因此，我们可以通过公式(19)来定义模型预测模块，其中，和分别用和来量化，可以用一个由和组成的矩阵来近似。通过逼近，我们可以简单地将和作为两个权重参数，在训练集中探索它们的最优值。虽然这种近似削弱了系统的表现能力，但它使控制器在变化的环境下更加鲁棒和稳定。需要注意的是，我们使用了矩阵和来建模动态系统，但这两个矩阵的确切值并不需要明确求出。如式(19)所示，我们利用这些矩阵来解决耦合效应，并得到仅有和确定的近似函数
