1 问题背景
在许多业务场景中,我们都遇到在约束条件下,如何求得业务目标最优的问题。
例如,在推荐或搜索场景中,我们的目标是最大化平台的总成交额(GMV),但是也有需要保证某些商家的流量的限制。对于新商家,如果按照贪心策略,按点击率预估来排序,头部商家会一直排前列,新商家得不到流量无法成长。这样对于平台的长期生态也是无益的。
还有在广告展现场景中,在广告商的预算预制条件下,通过分配每条流量的展现广告,达到最大化用户点击总和;
下面是只有两个流量和两个广告的例子。设有两个用户$u_1$和$u_2$,对广告$a_1$的点击率预估分别是0.8和0.7。对广告$a_2$的点击率预估分别是0.6和0.2。如果我们以点击率预估来做为收益的话,如果没有约束,则总体收益高的投放方式,是将广告$a_1$和$a_2$都投给流量$u_1$,得到收益$0.8+0.7=1.5$。

如果在有约束时,即一个广告只能投放一次。如果采用贪婪方法的话,流量$u_1$来时,我们选择当前收益最高的广告$a_1$进行投放。流量$u_2$来后,我们只好投放广告$a_2$,这样得到的收益是$0.8+0.2=1$。
但是考虑全局最优的话,我们如果对流量$u_1$投放广告$a_2$,对流量$u_2$投放广告$a_1$,则得到的收益是$0.6+0.7=1.3$。
另外,在线上营销系统中,我们可以按照预估点击率最高的奖品进行发放。但是如果奖品的数量是固定的, 那么怎么能够均匀的发放在各个时间段, 以及各类人群中 (如不同生命周期的人群)。这也是一个在约束条件下如何求得最优解的问题。
这些问题都属于在线分配问题(online allocation),即如何在有限的资源进行合理的分配。我们可以将问题抽像为如下。
这里$x_{ij}$为第$i$个流量分配给第$j$个商家的概率,$C_{ij}$为流量$i$分配给商家$j$时获得的收益。在排序场合,表示预估点击率。$B_{k}$为第$k$个商家本时段的目标流量。这里有$k$个不等式。
2 在线求解
在线上场景中,实时求解$x_{ij}$困难,我们可以把上述约束问题转化为拉格朗日对偶问题来求解,即把求解$x_{ij}$转化为求解$\alpha_{j}$,从而简化问题。
将上述问题添加类似熵的正则项,使得$x_{ij}$的分配更加均匀。添加正则项后其表达式如下。
其lagrange形式可以写成
由KKT条件,满足$\nabla_xL(x,\alpha,\beta)=0$和$1-\sum_jx_{ij}=0$,
得到
将上式$x_{ij}$代入$1-\sum_jx_{ij}=0$,得到下式
将$x$代入原式$L(x,\alpha,\beta)$,
最后,其对偶问题为
这是个关于 α 的最优化问题,用梯度下降(gradient descend)算法可以很好的求解,迭代更新如下,其中η 为步长:
我们来观察上式,如果分配超过约束$B_k$, 则$\alpha_k$增大,下一轮迭代中分配额就会减少,反之分配小于约束$B_k$,则获得的分配额增加,当$\alpha_k$等于0时,表示分配不再受这个约束影响,即为贪婪思想进行分配。
最后,针对此类在线求解流量分配问题时,步骤可如下。 步骤:
- 利用旧数据集,按时间段计算其约束值。
- 计算到目前为止的流量数。
- 根据最速下降法,计算$\alpha_k$的梯度为$B_k-\sum_{ij}b_{kij}x_{ij}^{t-1}$。
- 将$\alpha_k$存入在线存储,将商品根据$C_{ij}-\sum_k\alpha_kb_{kij}$重排序。
3 模拟问题
我们可以用一个小游戏来模拟流量分配问题。假设你有ABCD四种商品可供拍卖,每种商品的库存是有限的,分别为4,5,6,6。现在会有一批客户来对商品报价,每轮分别对ABCD进行报价,共报30轮。每轮你可以选择其中一种商品卖出或不卖出任何商品,目标是最大化我们的收入。
在每轮报价时,我们可以选择当轮最高价进行出售,即贪婪算法。但是在21轮报价后,库存已为0,但是后面可能会有更高的出价。我们也可以调整策略,当轮并不出售留待后面更高的报价。
其收入趋势如下图。