实时在线优化流量分配问题

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$

image.png

如果在有约束时,即一个广告只能投放一次。如果采用贪婪方法的话,流量$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),即如何在有限的资源进行合理的分配。我们可以将问题抽像为如下。

$$max_x \sum_{ij}C_{ij}x_{ij} $$
$$s.t. \ x_{ij} \in \{0,1\} $$
$$\sum_j x_{ij}=1 $$
$$\sum_{ij}b_{kij}x_{ij}\leq B_k,k=1,2,...,K $$

这里$x_{ij}$为第$i$个流量分配给第$j$个商家的概率,$C_{ij}$为流量$i$分配给商家$j$时获得的收益。在排序场合,表示预估点击率。$B_{k}$为第$k$个商家本时段的目标流量。这里有$k$个不等式。

2 在线求解

在线上场景中,实时求解$x_{ij}$困难,我们可以把上述约束问题转化为拉格朗日对偶问题来求解,即把求解$x_{ij}$转化为求解$\alpha_{j}$,从而简化问题。

将上述问题添加类似熵的正则项,使得$x_{ij}$的分配更加均匀。添加正则项后其表达式如下。

$$max_x \sum_{ij}C_{ij}x_{ij}-\lambda\sum_{ij}x_ {ij}lnx_{ij} $$
$$s.t. \ x_{ij} \in \{0,1\} $$
$$\sum_j x_{ij}=1 $$
$$\sum_{ij}b_{kij}x_{ij}\leq B_k,k=1,2,...,K $$

其lagrange形式可以写成

$$L(x,\alpha,\beta)=\sum_{ij}C_{ij}x_{ij}-\lambda\sum_{ij}x_{ij}lnx_{ij}+\sum_k\alpha_k(\beta_k-\sum_{ij}b_{kij}x_{ij}) +\sum_i\beta_i(1-\sum_jx_{ij}) $$

由KKT条件,满足$\nabla_xL(x,\alpha,\beta)=0$$1-\sum_jx_{ij}=0$,

$$\nabla_xL(x,\alpha,\beta)=C_{ij}-\lambda(1+lnx_{ij})-\sum_k\alpha_kb_{kij}-\sum_i\beta_i=0 $$

得到

$$x_{ij}=exp\frac{1}{\lambda}[(C_{ij}-\sum_k\alpha_kb_{kij})-\beta_i-\lambda] $$

将上式$x_{ij}$代入$1-\sum_jx_{ij}=0$,得到下式

$$\beta_i=\lambda(lnZ_i-1) $$
$$x_{ij}=\frac{1}{Z_i}exp(\frac{1}{\lambda}[C_{ij}-\sum_k\alpha_kb_{kij}]) $$
$$Z_i=\sum_jexp(\frac{1}{\lambda}[C_{ij}-\sum_k\alpha_kb_{kij}]) $$

$x$代入原式$L(x,\alpha,\beta)$

$$L(x,\alpha,\beta)=\lambda\sum_{ij}x_{ij}lnZ_{i}+\sum_k\alpha_{k}B_k $$
$$=\lambda\sum_ilnZ_i(\sum_jx_{ij})+\sum_k\alpha_{k}B_k=\lambda\sum_ilnZ_i+\sum_k\alpha_{k}B_k $$

最后,其对偶问题为

$$min_{\alpha\geq0}\lambda\sum_ilnZ_i+\sum_k\alpha_{k}B_k $$

这是个关于 α 的最优化问题,用梯度下降(gradient descend)算法可以很好的求解,迭代更新如下,其中η 为步长:

$$\alpha_k^t=max\{0,\alpha_k^{t-1}-\eta(B_k-\sum_{ij}b_{kij}x_{ij}^{t-1})\} $$

我们来观察上式,如果分配超过约束$B_k$, 则$\alpha_k$增大,下一轮迭代中分配额就会减少,反之分配小于约束$B_k$,则获得的分配额增加,当$\alpha_k$等于0时,表示分配不再受这个约束影响,即为贪婪思想进行分配。

最后,针对此类在线求解流量分配问题时,步骤可如下。 步骤:

  1. 利用旧数据集,按时间段计算其约束值。
  2. 计算到目前为止的流量数。
  3. 根据最速下降法,计算$\alpha_k$的梯度为$B_k-\sum_{ij}b_{kij}x_{ij}^{t-1}$
  4. $\alpha_k$存入在线存储,将商品根据$C_{ij}-\sum_k\alpha_kb_{kij}$重排序。

3 模拟问题

我们可以用一个小游戏来模拟流量分配问题。假设你有ABCD四种商品可供拍卖,每种商品的库存是有限的,分别为4,5,6,6。现在会有一批客户来对商品报价,每轮分别对ABCD进行报价,共报30轮。每轮你可以选择其中一种商品卖出或不卖出任何商品,目标是最大化我们的收入。

在每轮报价时,我们可以选择当轮最高价进行出售,即贪婪算法。但是在21轮报价后,库存已为0,但是后面可能会有更高的出价。我们也可以调整策略,当轮并不出售留待后面更高的报价。

其收入趋势如下图。 Image