KDD2021 | USCB:展示广告约束出价问题的通用解决方案-程序员宅基地

技术标签: 算法  python  机器学习  人工智能  大数据  

▐  导读

实时竞价是在线广告的经典问题,是广告商获得目标流量的重要工具。在本文中,我们将广告商对流量需求进行整合,提出了带预算以及KPI约束下最大化流量价值的带约束出价建模框架,并推导出了通用的最优出价公式,利用 rl 算法调节该公式中的参数,实现了实时流量环境下广告商的流量效果最优。目前,该方法已应用于阿里妈妈展示广告场景,基于该工作撰写的论文已发表在 KDD 2021。本文将对在线展示广告约束出价问题的通用解决方案展开介绍,希望可以对从事相关工作的同学带来启发或帮助。

论文:https://dl.acm.org/doi/pdf/10.1145/3447548.3467199

▐  背景

在线展示广告场景下,广告主通常以实时竞价的方式获取曝光机会。在大多数广告平台,广告主最常见的需求就是在预算及某些KPI约束下最大化竞得流量的价值(如在预算和点击成本约束下最大化点击量)。每个广告主的投放需求在营销目标(如点击、曝光)、KPI约束类型(如点击成本上界、点击率下界)以及KPI约束数量三个维度上都有很大不同。现有的研究通常局限于某个特定的投放需求,缺乏通用性,或者很难达到最优投放结果。

在本文中,我们将广告主的各种投放需求形式化为约束出价问题,并推导出了通用的最优出价策略。对于每个广告投放计划来说,其最优出价公式由m个参数组成,m为约束数量。然而在实际应用过程中,由于参竞环境不断波动,确定每天的最优出价参数是很困难的事。针对该问题,本文提出了一种强化学习方法,该方法会在计划投放过程中根据投放状态动态调整出价参数,使其尽可能逼近最优参数。其中,我们基于约束出价问题的子问题特性,对强化学习训练过程进行了优化,使其能够更快地收敛到最优解。我们将这种方法称为 Unified Solution to Constrained Bidding in Online(以下简称:USCB)。USCB在工业场景真实数据集上取得了很好的效果,与此同时,该方法已经在阿里妈妈广告投放策略平台成功部署,为各个业务线提供出价参数调控服务,为平台收入与广告主投放效果带来了显著提升。

▐  形式化建模

在预算及某些KPI约束下最大化竞得流量的价值(如在预算和点击成本约束下最大化点击量)可以建模为带约束的优化问题。

在一段时间内(例如一天),假设有个按顺序到达的流量(下标为i)。在一个 SPA(广告流量将分配给出价最高的出价人,成本为第二个的最高出价)计费模式、CPM(按照展现扣费)扣费方式的 RTB 系统(实时竞价系统)中,广告商提供出价 以实时竞争每条流量。代 表了广告主是否能够赢得流量 i。如果广告主出价 高于最高出价 ,则将赢得流量 (此时 ),最终展现的成本为 .

在获取流量过程中,广告计划的目标是最大化赢得流量的总价值,即最大 , 其中 代表流量i的价值。预算B和KPI约束对于控制广告效果至关重要。预算约束可视为 ,即获取流量的总成本要不大于预算B。KPI约束更为复杂,可分为两类。第一类是成本相关(CR)约束,它限制广告的平均单位成本,如 CPC(平均点击成本)和 CPA(平均转化成本)等。第二类是非成本相关(NCR)约束,它限制了广告的平均效果,如 CTR(平均点击率)。KPI 约束的统一表达 可由式(1)表示:

dd455bc3f74f64e8577806635a6d5ebd.png

其中,k 是广告商设置的约束j的上界, 和 根据约束不同而具体定义,例如点击成本约束时,为,为,为广告商设置的点击成本上限。点击率约束时,为,为,为广告商期望最小点击率的倒数。

因此,考虑到广告目标、预算和 个 KPI 约束,计划的诉求可以通过(LP1)表示为统一的带约束竞价问题。

9ba3e7b75d3917aa3bdb9358544510f7.png

如果知道完全的流量集合,即知道该计划能触达的每条流量i的流量价值 ,成本 等,则可以通过一般的求解线性规划问题(LP1)的解法可得到最优解 。然而,在实际应用中,需要在流量集未知的情况下进行实时竞价,而且由于在线展示广告每日访问用户和每日参竞计划数量众多且随机性很大,也很难通过准确的预测输入流量的方式构造出流量集,因此常规的线性规划求解方法无法应用。本文则构造出了一个最优出价公式,将问题转化为求解最优出价公式里的最优参数的问题,大大降低了在线情况下求解该问题的难度。

▐  最优出价公式

最优的出价公式为:

其中, 是常数项, 是参数,其范围为:。如果约束j是CR,则 ;如果约束 j 是 NCR,则 ,证明过程详见论文。

最优出价公式共包含 m+1 个核心参数 , ∈ [0, ..., ],公式中剩余项为在线流量竞价时可获取的流量上的信息。由于最优出价公式的存在,针对此类具有预算约束和 M 个 KPI 约束,且希望最大限度地提高竞得流量的总价值的问题,最优解可以通过找到 M+1 个最优参数依据公式来进行出价,而不是为每个流量分别寻找最优的出价。

▐  参数调整方法

定义了最优出价公式后,剩余的挑战是计算最优参数, ∈ [0,...,]. 因为流量在不同时段波动很大,通过离线日志求解获得的历史最佳参数不能完美适用于当前的流量环境。因此,在实际应用中,需要开发一个参数调整模块,该模块使用调控策略将 修正到能适应当前环境(即广告的状态,包括预算支出状态、KPI 约束满足状态等)的最佳 。该过程可以描述为一个马尔可夫决策过程 MDP,并通过强化学习的方法求解最优调控策略,r=1,..,T 时刻下,通过感知广告的状态,调节 到最优,使得整体获得最大的流量价值:

  • St: 广告 t 时刻预算消耗和满足约束的状态,如剩余时间、剩余预算、预算消耗速度、约束的当前 KPI 比率等。

  • At: 参数 的调节幅度

  • : t 时刻中,竞得流量的总价值。

由于模型 T 是广告状态转移的过程,我们采用强化学习的方法为 model free 的方法,可将其看作黑盒。

利用 MDP 对该问题进行建模后,使用强化学习的经典算法 DDPG[1] 对该问题进行求解,强化学习算法一般需要大量的样本,且收敛速度较慢,为了加快 RL 的收敛速度,我们结合带约束的竞价问题的自身特性,设计最优策略的模式,缩小了策略空间。为解释该优化逻辑,我们首先引入子问题特性的概念:

由于流量在一天之内依次到达,在任意 t 时刻,最优化整体的流量价值的建模可以转化为如下形式:

3eab52b8947b29f23c78e9960dec9a18.png

其中 v#,c#,p# 等表示 t 时刻之前已经获得流量价值,总成本等。可证明该子问题的最优出价公式为:

其最优出价公式的形式与原问题 LP1 是类似的。想要达到该子问题的最优解,需要在t时刻求的最优参数,并一直持续下去。因此最优的策略为调整当前的参数 直接到最优参数 ,并且在后续流量上保持不动。

在此最优策略的基础上,我们将 critic 网络优化目标定义为最小化 G 与 之间的差距。G 为整个决策周期,策略真实的归一化累积奖赏,即:

其中,R 为累积到 t 时刻的流量价值,V 为使用当前的参数并固定不动后剩余流量上能产生的价值。pj 为约束的惩罚项。为模型预估的累积奖赏。与传统的 DDPG 算法利用 来更新 critic 网络相比,我们的方法会让 Q 学的更容易,能提升整体网络的收敛速度。最终算法为:

ef9460e31468c350ecd5997e1004ad8e.png

▐  实验效果

淘宝广告系统当前包含三种典型的带约束的最大化价值的出价产品:

  • CB{click}:预算约束下最大化点击量。出价公式为:

  • CB{click-CPC}:预算和 cpc 成本约束下最大化点击量。出价公式为:

  • CB{conversion-CPC}:预算和cpc成本约束下最大化转化量。出价公式为:

选择三种类型的计划构建实验数据集为:

87ca8fa193c6a3b04cf33a8432a3ae30.png

其中,imporession 代表计划日均参竞流量的大小,deviation 指标表征计划的最优出价参数的天级差异。

03439a9ed1378773c0e849db5cb2db3c.png

在最优出价公式下,对比三种调控方法:

  • FB:用历史固定参数。

  • M-PID:《Bid optimization by multivariable control in display advertising》里的基于模型的 pid 方法[2]。

  • DRLB:《Budget constrained bidding by model-free reinforcement learning in display advertising》里提出的解决预算约束问题的 rl 方法[3]。

效果指标为R/R*,其中 R 为利用调控算法获得的流量价值,R* 为利用线性规划求解出的最优流量价值。

934c8ccbffd059f03b99a23fcbaafe6c.png

在不同的最优参数离散程度及不同的产品类型下,USCB的效果都是最好的。

▐  在线部署

在淘宝显示广告系统中,已经部署了约束性竞价的通用解决方案(USCB)并进行了合理的论证。该在线部署策略为成千上万的广告客户提供服务,每天影响数百万的收入。算法应用程序的架构显示在图中。模型的培训和部署是并行的,这使得模型能够有效地重复,并且可以轻松地应用于大量的广告活动。

85ca2911b365f78718434cb6ce38f3bc.png

▐  结论

本文针对在线展示广告中的带约束竞价问题提出了通用有效的解决方案。首先抽象出了广告商的核心需求,并将其表述为一个约束竞价问题,利用对偶方法推导了 SPA 下的最优竞价函数。最优竞价函数通过调整有限的参数为广告商提供在所有流量上实时竞价的服务。为了解决环境变化过快导致参数在连续几天之间出现偏差的问题,本文进一步提出了一种 RL 方法来动态调整参数。此外,本文还发现约束竞价问题是一个递归最优问题,这一性质显著地促进了学习过程的收敛过程。通过全面的实验验证了我们的解决方案的有效性。本文中推导的公式和 RL 方法一起被称为约束竞价通用解决方案(USCB),该方案已在淘宝广告平台上部署并验证。

▐  关于我们

我们是阿里妈妈展示广告机制策略算法团队,致力于不断优化阿里展示广告技术体系,驱动业务增长,推动技术持续创新;我们不断升级工程架构以支撑阿里妈妈展示广告业务稳健&高效迭代,深挖商业化价值并优化广告主投放效果,孵化创新产品和创新商业化模式,优化广告生态健壮性;我们驱动机制升级,并已迈入 Deep Learning for Mechanisms 时代,团队创新工作发表于 KDD、ICML、CIKM、WSDM、AAMAS、AAAI 等领域知名会议。在此真诚欢迎有ML背景的同学加入我们~

投递简历邮箱(请注明-展示广告机制策略):[email protected]

参考文献

[1] Lillicrap T P, Hunt J J, Pritzel A, et al. Continuous control with deep reinforcement learning[J]. arXiv preprint arXiv:1509.02971, 2015.

[2] Yang X, Li Y, Wang H, et al. Bid optimization by multivariable control in display advertising[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 1966-1974.

[3] Wu D, Chen X, Yang X, et al. Budget constrained bidding by model-free reinforcement learning in display advertising[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 2018: 1443-1451.

END

7b3be018b30632a9554b9e383e71a678.gif

欢迎关注「阿里妈妈技术」

eb9a7925b0f8fc11f28c2a36008d3408.gif

疯狂暗示↓↓↓↓↓↓↓

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/alimama_Tech/article/details/120559268

智能推荐

深入分析MPU6050在ESP32的实现流程_esp32 mpu6050-程序员宅基地

文章浏览阅读1k次。概念与操作描述一种用于在集成电路之间进行数据传输的串行通信协议。主设备(Master)发起通信并控制整个数据传输过程的设备。从设备(Slave)被动响应主设备请求的设备。数据线(SDA)双向的数据线,用于传输数据。时钟线(SCL)主设备通过时钟线控制数据的传输速率。地址每个从设备在总线上具有唯一的地址,用于识别设备。读写操作主设备向从设备发送读取或写入命令,用于读取从设备的数据或向从设备写入数据。应答(ACK/NACK)_esp32 mpu6050

畅购商城第五天_商城系统 es商品搜索排序-程序员宅基地

文章浏览阅读736次。第5章 商品搜索学习目标Elasticsearch安装docker安装Elasticsearch系统参数问题跨域操作IK分词器配置Kibana的使用->DSL语句Kibana->DSL语句操作->ElasticsearchES导入商品搜索数据Sku数据导入到ElasticsearchMap数据类型->Object关键词搜索->能够实现搜索流程代码的编写分类统计搜索1. Elasticsearch 安装我们之前已经使_商城系统 es商品搜索排序

(BDCI-CCF)出租车发票识别_出租车发票识别ccf-程序员宅基地

文章浏览阅读3.1k次,点赞4次,收藏16次。参考文章:​​​​​​百度AI攻略:出租车票识别_才能我浪费的博客-程序员宅基地附完整python源码)基于tensorflow、opencv的入门案例_发票识别一:关键区域定位_小白来搬家-程序员宅基地_python发票识别注:感谢一起完成项目的队友们大赛官网:出租车发票识别 Competitions - DataFountain一、赛题说明1.赛题背景出租车发票在日常财务发票报销中较为常见,由于这类发票样式丰富,区域性特点明显,并且包含大量模糊字迹和错位字迹,因此准确的定位发票_出租车发票识别ccf

c++协程3 (boost::coroutine)_c++ boost什么版本支持协程-程序员宅基地

文章浏览阅读2.6k次。#include #include #include #include using boost::coroutines::coroutine;void cooperative(coroutine>::pull_type &source){ auto args = source.get(); std::cout (args) (args) << '\n'; source()_c++ boost什么版本支持协程

数据结构与算法 - 线性表(完整代码)_线性表完整程序代码-程序员宅基地

文章浏览阅读5.3k次,点赞7次,收藏32次。样例输入:3 //输入一个数a,后面将输入a个数据元素8 9 3 //a个数据元素,依次插入尾结点后。形成单链表结点序列:8,9,33 //输入一个数b,后面将再输入b个数据元素10 89 22 //b个数据元素,依次插入0号结点后。形成单链表结点序列:8,22,89,10,9,389 //删除一个值为89的结点1 //删除1号结点样例输出:8 10 9 3#inc..._线性表完整程序代码

fastjson自动过滤null值解决方案_fastjson parseobject 过滤值为null的字段-程序员宅基地

文章浏览阅读2.7k次,点赞2次,收藏2次。fastjson转换字符串自动过滤value为null的问题背景:使用 JSON.toJSONString(Object object)的时候发现打印出来的字符串少了几个字段,以为代码没走相应的逻辑,发现少的都是value为null的字段,发现是fastjson自动把value为null的字段过滤了。解决办法:设置SerializerFeature序列化属性 SerializerFeatu..._fastjson parseobject 过滤值为null的字段

随便推点

nodejs如何调用电脑上的软件读取目标文件-程序员宅基地

文章浏览阅读76次。可以使用 Node.js 的子进程模块来调用电脑上的软件。例如,假设你想使用电脑上的 cat 命令来读取文件,你可以这样写:const { spawn } = require('child_process');const cat = spawn('cat', ['path/to/file']);cat.stdout.on('data', (data) => { console..._nodejs 打开软件

Kubernetes + CRI + Kata + Firecracker -程序员宅基地

文章浏览阅读835次。KataKata源自希腊文Καταπίστευμα(ka-ta-PI-stev-ma),原意是值得信任的人,kata container正是解容器安全的问题而诞生的。传统的容器是基于namespace和cgroup进行隔离,在带来轻量简洁的同时,也带来了安全的隐患。事实上容器虽然提供一个与系统中的其它进程资源相隔离的执行环境,但是与宿主机系统是共享内核..._kata+stratovirt

[转]使用C#进行点对点通讯和文件传输(发送接收部分)-程序员宅基地

文章浏览阅读131次。上面介绍了通讯的基类,下面就是使用那个类进行发送和接收的部分: 二、发送部分: 发送咱们使用了多线程,可以同时进行多个任务,比如发送文件、发送文本等,互不影响: 发送文本方法: private void StartSendText(string strHost,int iPort,string strInfo) { SendText stText = new SendText(strHost,iP..._c# edi 报文发送接收

swift5.5异常的处理的三种的方式_swift5 运行时异常-程序员宅基地

文章浏览阅读179次。swift5.5异常的处理的三种的方式override func viewDidLoad() { super.viewDidLoad() method1() method2() method3() } func method3(){ //方式3 太危险,直接强制解包 不推荐 let pattern = "abc" let regex = try! NSRegularExpre_swift5 运行时异常

illumina 二代测序原理及过程_illumina测序原理及流程-程序员宅基地

文章浏览阅读1.1w次,点赞14次,收藏87次。illumina 二代测序原理及过程_illumina测序原理及流程

rosbag record -a -O cmd_record命令产生.bag.active,如何将其转换成.bag文件,执行rosbag play cmd_record.bag命令呢?_rosbag record生成bag-程序员宅基地

文章浏览阅读2.1k次,点赞2次,收藏12次。看了某站古月居的ROS视频,听着视频,看老师操作感觉很简单,自己跟着做了一遍,发现并不简单,为啥出现了好多奇怪的问题。 下面是解决将.bag.active转换成.bag文件的详细步骤!其中cmd_record是文件名。1、先用 $ rosrun turtlesim turtlesim_node 命令调出小海龟,然后让它走两步。2、之后用命令 $ rosbag record -a -O cmd_record 记录数据。..._rosbag record生成bag

推荐文章

热门文章

相关标签