RTB竞价策略学习

背景

近一年的工作基本是围绕着广告ctr/cvr模型优化展开的，但是对竞价广告整体框架还是缺乏了解，最近准备学习一下RTB相关的内容，笔记主要围绕着Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting 这篇文章学习

Bid Landscape Forecasting

在RTB中，作为广告主(或者DSP方)而言，关键问题其实是2个，一个是是否应该出价，第二个是应该出多少价，对于第一个问题，一般可以根据广告素材的预估ctr/cvr等判断预期收益决定，对于第二个问题则比较复杂一点；因为在RTB中，只有竞价成功了才能知道真实的计费是多少(对于一价而言就是bid，对于二价而言则需要看其他的报价)，由于在每次报价之前不知道其他的报价，因此需要根据历史的一些统计经验值或者模型来预估本次出价，这个就是bid landscape forcasting.

了解几个基本的概念：

winning probability: 给定出价 $b_x$bx​ 和广告特征 $x$x 单次请求赢得展示的胜率 $P(win|x,b_x)$P(win∣x,bx​)
$q_x(x) \equiv P(win|x,b_x) \cdot p_x(x)$qx​(x)≡P(win∣x,bx​)⋅px​(x)
其中 $q_x(x)$qx​(x) 表示广告得到展示的概率，$p_x(x)$px​(x) 表示发起竞价的概率， $P(win|x,b_x)$P(win∣x,bx​) 表示竞价的胜率

假设我们已经知道市场上出价z的分布 $P_z(z)$Pz​(z) ,那么胜率可以描述为：
$w(b_x) \equiv \int_o^{b_x}p_z(z)dz$w(bx​)≡∫obx​​pz​(z)dz

几种常见的bid landscape forecasting

Tree-based log-normal model

这种方法来自Yahoo的一篇文章Bid Landscape Forecasting in Online Ad Exchange Marketplace，方法是对于adset级别的广告素材，先将历史统计的竞价信息按照特征树的方式先做一个树路径划分，每个树的路径的叶子节点值是match这个特征路径的bid，文章对这种树结构做了一个优化：对于不存在的节点将以*补充，如下图所示：

特征树划分好之后，使用GBDT去拟合历史报价，从而学习到每条路径的预估bid值，当一个新的request来的时候，则可以根据match到路径的预估值和历史报价进行本次报价预估均值和标准差。在获取到每个adset级别的均值 E[s] 和标准差 std[s] 之后,文章假设每个adset的bid分布是对数正态分布：
可以求解到
对于campaign级别的竞价，paper假设一个campaign的bid是这个campaign下面每个adset的混合分布：其中

censored linear regression

线性拟合方法就比较简单，对于广告素材 x ,使用一个参数 \beta 来拟合出价bid：$\hat{z} = \beta x$z^=βx , Pre- dicting winning price in real time bidding with censored data 这篇paper用下面的似然函数来建模：

本质上是对于win的事件，让 $\beta x$βx 尽量去拟合bid，对于lose的事件，让 $\beta x$βx 尽量出价比bid高点

survival model

survival model是一种基于统计的预估出价(二价)分布模型，实现步骤如下
将所有出价历史按照bid从小到大排序成 $<b_i,w_i,z_i>_{i=1...N}$<bi​,wi​,zi​>i=1...N​ ,其中 $b_i$bi​ 是第i次的出价，$w_i$wi​表示是否赢得此次出价，$z_i$zi​表示本次胜出的价格
将上述的数据按照bid从小到大转换成 $<b_j,d_j,n_i>_{j=1...M}$<bj​,dj​,ni​>j=1...M​ 形式，其中dj表示胜出价为$b_{j}-1$bj​−1胜出的次数，$n_j$nj​表示出价为$b_j$bj​-1不能胜出的次数，以下面示例图为例，当计算$b_j$bj​=3的时候，那么$d_j$dj​=1(wining_prirce为$b_j$bj​-1的胜出次数)，$n_j$nj​为4(出价为$b_j$bj​-1时候失败的次数)。本质上计算的是当bid增加一块钱(假设单位是元)胜出的概率为： $\frac{d_j}{n_j}$nj​dj​​ ,对应的lose概率为 $\frac{n_j-d_j}{n_j}$nj​nj​−dj​​
对于出价为$b_x$bx​,lose的概率为$l(b_x) = \prod_{b_j<b_x}\frac{n_j-d_j}{n_j}$l(bx​)=bj​<bx​∏​nj​nj​−dj​​，win的概率为$w(b_x) =1- \prod_{b_j<b_x}\frac{n_j-d_j}{n_j}$w(bx​)=1−bj​<bx​∏​nj​nj​−dj​​

竞价策略优化

竞价策略主要针对广告需求方，根据每次请求的context(广告素材、用户行为等)判断需不需要出价以及出多少价，主要流程可以用下图描述：

和搜索广告不同的是，RTB是针对每次的展示竞价，而不是针对搜索关键词出价，因此RTB对广告主(或者DSP)来说，需要更实时且精准的预估.
RTB竞价策略通常包括两个部分：Utility Estimation和Cost Estimation。Utility Estimation一般指赢得这次展示的期望收益，比如点击率/转换率等；Cost Estimation则指的是赢得此次竞价需要的成本，可以用下图描述：

单广告计划bid optimisation

继续了解几个概念

1. 给定市场出价概率密度分布Pz(z)和出价b，对应的胜率为 $w(b)=\int_0^bp_z(z)dz$w(b)=∫0b​pz​(z)dz
2. 广告的预期回报为 $u(r)$u(r) ,$u(r)$u(r)依赖具体的广告策略，如果广告希望回报是点击数，那么 $u_{clk}(r)=r$uclk​(r)=r ;如果广告希望回报是利润，每次点击的收益是$v$v，那么 $u_{profit}(r,z)=vr-z$uprofit​(r,z)=vr−z
3. cost(如果胜出了，需要花费的成本):
   对于一价广告， $c(b)=b$c(b)=b
   对于二价广告， $c(b)=\frac{\int_0^bzp_z(z)dz}{\int_0^bp_z(z)}$c(b)=∫0b​pz​(z)∫0b​zpz​(z)dz​
4. $T$T: 广告计划的规则和生命周期决定的拍卖量
5. $B$B:广告计划的预算budget

Truth-telling bidding

true-telling bidding是只考虑竞价回报，而不考虑预算的场景，期望收益为
$U_{profit}(b(.)) = T\int_r\int_{z=0}^{b(r)}u_{profit}(r,z)p_z(z)dzp_r(r)dr = T\int_r\int_{z=0}^{b(r)}(vr-z)p_z(z)dzp_r(r)dr （1）$Uprofit​(b(.))=T∫r​∫z=0b(r)​uprofit​(r,z)pz​(z)dzpr​(r)dr=T∫r​∫z=0b(r)​(vr−z)pz​(z)dzpr​(r)dr（1）
这个相当于是Lagrange无约束优化问题，直接对出价$b(.)$b(.)求导
(1)式对 b(.) 求导得到：$(vr-b(r))*p_z(b(r))*p_r(r)=0$(vr−b(r))∗pz​(b(r))∗pr​(r)=0由此得到出价 $b_r = vr$br​=vr
Truth-telling bidding仅适用于不限budget以及不限拍卖量的情况

Linear Bidding

线性出价则简单的多，基本公式是
$b_{lin} = \phi vr$blin​=ϕvr
其中参数 $\phi$ϕ 是根据训练数据训练出来的值

预算约束下的bidding

在拍卖量T和预算B受约束的情况下，优化目标变成：
$max_{b()} T\int_ru(r)w(b(r))p_r(r)dr$maxb()​T∫r​u(r)w(b(r))pr​(r)dr
$st: T\int_rc(b(r))w(b(r))p_r(r)dr=B （2）$st:T∫r​c(b(r))w(b(r))pr​(r)dr=B（2）
显然，这是一个等式约束条件下lagrange优化问题，自然的，引入lagrange算子 $\lambda$λ
$l(b(r),\lambda) = T\int_ru(r)w(b(r))p_r(r)dr - \lambda (T\int_rc(b(r))w(b(r))p_r(r)dr-B) l(b(r),\lambda) = T(\int_ru(r)w(b(r))p_r(r)dr - \lambda (\int_rc(b(r))w(b(r))p_r(r)dr)+\frac{B}{T}\lambda)$l(b(r),λ)=T∫r​u(r)w(b(r))pr​(r)dr−λ(T∫r​c(b(r))w(b(r))pr​(r)dr−B)l(b(r),λ)=T(∫r​u(r)w(b(r))pr​(r)dr−λ(∫r​c(b(r))w(b(r))pr​(r)dr)+TB​λ)
等价于优化
$\int_ru(r)w(b(r))p_r(r)dr - \lambda (\int_rc(b(r))w(b(r))p_r(r)dr)+\frac{B}{T}\lambda （3）$∫r​u(r)w(b(r))pr​(r)dr−λ(∫r​c(b(r))w(b(r))pr​(r)dr)+TB​λ（3）
求解过程：
令$b(r)$b(r)求导值为0可得：
$\lambda w(b(r))\frac{\partial c(b(r)}{\partial b(r)} = (u(r)-\lambda c(b(r)))\frac{\partial(w(b(r)))}{\partial b(r)} （4）$λw(b(r))∂b(r)∂c(b(r)​=(u(r)−λc(b(r)))∂b(r)∂(w(b(r)))​（4）
令对 $\lambda$λ 求导值为0可得：
$T\int_rc(b(r))w(b(r))p_r(r)dr=B（5）$T∫r​c(b(r))w(b(r))pr​(r)dr=B（5）

1. 对于一价场景
   $c(b(r))=b(r)$c(b(r))=b(r)
   假设初始$z$z服从 $p_z(z)=\frac{l}{(l+z)^2}$pz​(z)=(l+z)2l​这一分布, $\frac{l}{(l+z)^2}$(l+z)2l​对应的原函数为$-\frac{l}{l+z}$−l+zl​
   同时假设 $p_z(z)$pz​(z) 服从均匀分布
   $w(b(r))=\int_0^{b_r}p_z(z)dz=\frac{b(r)}{l+b(r)}$w(b(r))=∫0br​​pz​(z)dz=l+b(r)b(r)​

   带入4式和5式：
   $\lambda \frac{b(r)}{l+b(r)} = (u(r)-\lambda b(r))\frac{l}{(l+b(r))^2} T\int_0^1b(r)\frac{b(r)}{b(r)+l})dr=B$λl+b(r)b(r)​=(u(r)−λb(r))(l+b(r))2l​T∫01​b(r)b(r)+lb(r)​)dr=B
   由此求得：
   $b_{orthb}=\sqrt{\frac{u(r)l}{\lambda}+l^2}-l$borthb​=λu(r)l​+l2​−l
   同理，如果 $p_zz$pz​z 服从 $\frac{1}{l}$l1​ 的分布，可最终得到 $b(r) = r\sqrt{\frac{3Bl}{T}}$b(r)=rT3Bl​​

2. 对于二价场景
   $c(b(r))=\frac{\int_0^{b(r)}zp_z(z)dz}{\int_0^bp_z(z)}$c(b(r))=∫0b​pz​(z)∫0b(r)​zpz​(z)dz​
   和上面相似的求解方法可以得到：
   $b_{ortb-lin}(r)=\frac{u(r)}{\lambda}$bortb−lin​(r)=λu(r)​
   如果 $p_zz$pz​z 服从 $\frac{1}{l}$l1​ 的分布,同时假设 $p_z(z)$pz​(z) 服从均匀分布
   类似的可以求解：
   $b(r) = 2r^3\sqrt{\frac{Bl^2}{T}}$b(r)=2r3TBl2​​

多广告计划bid optimisation (待续)