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

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

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