RTB竞价流控-budget pacing

前言

前一篇写了关系rtb bidding stragegy的相关内容，这一篇主要介绍的是RTB竞价中的流控策略：budget pacing，主要内容是让广告主预算平稳花完，防止出现预算突然花完这种情况。[注：本笔记主要围绕着Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting 这篇文章学习]

budget pacing

budget pacing主要包括两个方法：节流和预算调整，其中节流控制的是参竞率，预算调整表示的是在每次原始出价 $b_i$bi​ 上进行修改出价。

节流: throttling

假设广告一天的预算B需要在T个时间窗口内花完:
$[b_1,b_2...b_T]$[b1​,b2​...bT​] $\sum_t^Tb_t=B$∑tT​bt​=B
$x_i$xi​ 表示第i次是否参竞，则节流所描述的问题可以表示如下：

由于未来的 $v_i$vi​ 、$c_i$ci​ 均未可知，因此上述方法不可求解，论文 Real time bid optimization with smooth budget delivery in online advertising将原始问题转化为：

其中 $s_t$st​ 表示t时间实际的花费，假设cpm稳定的情况下， $s_t$st​ 直接正比于展示量：

根据上面的式子，pacing_rate(t+1)可以表示为：

也就是说，t+1时间的pacingrate可以按照前一轮(t时间)的pacing_rate、胜率、请求量等参数，以及t+1时间内的的实际竞价情况进行调整

预算调整：bid modification

bid modification是对每次出价进行一个调整，此处介绍一种比较常见的算法：PID pacing
pid算法详细内容可参考这篇文章
确定有穷自动机：PID控制算法原理（抛弃公式，从本质上真正理解PID控制）
论文Feedback Control of Real-Time Display Advertising 详细介绍了PID算法在rtb bid modification中的应用，此处也是采样论文的方法进行介绍.
算法描述为：

其中 $\varepsilon(t_k)$ε(tk​)表示第k次的误差，比如天级预算是B,当前已经花的预算是 $b_k$bk​ ,则 $\varepsilon(t_k)=B-b_k$ε(tk​)=B−bk​
原始的出价为 $b_t$bt​ 最终的出价为：
$b_a(t)=b(t)exp(\phi(t))$ba​(t)=b(t)exp(ϕ(t))
当 $\phi(t)=0$ϕ(t)=0 时，表示不作调整