CBRL：面向ROI约束竞价问题的课程引导贝叶斯强化学习框架

丨目录：

· 摘要

· 背景

· 问题定义与MDP建模

· CBRL: 课程引导的贝叶斯强化学习框架

· 实验

· 总结与展望

· 参考文献

1. 摘要

实时广告竞价（Real-Time Bidding, RTB）是互联网在线广告中的核心问题之一，也是实现流量高效分配和广告定向投放的重要机制之一。为了在RTB中获得期望的广告投放效果，商家广告主通常需要采用竞价策略来满足多样化的需求。其中投入产出比（Return-on-Investment，ROI）约束是效果类广告主非常关注的一类诉求。我们发现，由于 ROI 非单调下降的特点，以及 ROI 约束与优化目标间常出现的跷跷板效应，约束竞价问题中 ROI 约束常难以满足。这一点在市场环境多变且存在外部博弈的投放场景上尤为显著和棘手。过去的工作由于通常假设市场环境相对稳定不变，其所设计的竞价策略难以在非稳态和部分观测下的广告市场中平衡好约束和目标最大化之间的权衡。本文探讨了非稳态市场下的 ROI 约束广告竞价问题。我们提出了部分可观测约束的 MDP 建模方式，利用了示性函数不引入额外参数地处理约束条件，开发了一个由课程引导的贝叶斯强化学习（Curriculum-Guided Bayesian Reinforcement Learning，以下简称CBRL）框架来数据驱动地学习竞价策略，该方法能够在非稳态的广告市场中，自适应地调节约束条件和目标之间的权衡。大量的实验结果验证了该方法在稳定性、学习效率、分布内和分布外泛化能力上的优越表现。基于该项工作整理的论文已经发表在 KDD 2022，欢迎感兴趣的同学阅读交流。

论文：ROI-Constrained Bidding via Curriculum-Guided Bayesian Reinforcement Learning

下载（点击↓阅读原文）：https://dl.acm.org/doi/abs/10.1145/3534678.3539211

2. 背景

实时广告竞价（RTB[1]）已经成为互联网流量商业化的重要渠道之一，它服务于大量效果类广告主，其每日吞吐流量可以超过万亿级。在 RTB 中，每一条流量均会触发一次用户的广告展现机会，不同的商家通过程序化出价代理（programmatic buying agents）参与到广告展现触发的在线拍卖中。在这样实时在线的序列化广告竞价过程中，广告主的诉求通常是最大化目标投放效果并且满足预算等金融性约束。在各种需求中，效果类广告主关注的一类诉求通常是投入产出比（ROI）约束。ROI 计算了单位成本的（各种类型的）回报，例如单位成本的点击数（Click per Cost, CPC）等，可以直观地反映金融资源的使用效率。

ROI 约束下的竞价问题具有一些独特的挑战。一方面，ROI 分子上的效用和分母上的成本可以以不同的速率变化，因此 ROI 是非单调的，而过去针对预算约束竞价问题设计的方法（详见[2]的调研）基于预算单调性导出的pacing策略往往不适合直接用于处理 ROI 约束。另一方面，由于效用与成本随出价提高而增长的速率不同，ROI 约束与最大化目标之间通常存在跷跷板效应，而这一现象在市场环境多变且存在外部博弈的站外投放场景尤为显著和棘手。尽管近期有一些工作[3]提出通过引入额外超参数来显式地控制约束目标权衡，但是它们通常假设静态或者相对稳定的市场环境，所设计的算法无法适用于更加动态变化的市场环境。更为严峻地是，广告主仅能通过扣费来感知市场的变化（例如对手策略的变化、媒体拍卖机制的变化），使得竞价策略难以针对性地调整。

针对这样非稳态市场下的 ROI 约束竞价问题，我们提出了一个部分观测约束的 MDP 建模，并且介绍了一种采用硬间隔来处理非单调约束的方法。该方法利用示性函数来处理约束条件，并开发了一个课程引导的贝叶斯强化学习（Curriculum-Guided Bayesian Reinforcement Learning，简称CBRL）框架来进行高效的策略学习以及约束目标权衡的自适应控制。我们在工业场景真实数据的不同问题设定上验证了 CBRL 在稳定性、学习效率、分布内和分布外泛化能力的优越表现。

3. 问题定义与MDP建模

3.1 ROI-Constrained Bidding

图1. RTB系统一次广告拍卖的流程

本文研究的 ROI 约束竞价问题（ROI-Constrained Bidding, RCB）具体指，在确定的时间周期内（通常考虑一天），竞价策略需要在满足指定ROI约束时最大化总收入。本文假设采用二价拍卖机制[8]，即竞得者按其他参竞者最高出价扣费。问题的形式化定义如下，一名参竞者获得请求 (和用户、广告、上下文有关的特征），基于效用预估 返回出价 。在胜出时，广告主从系统获得反馈包括：实际的收入 ，实际的支出 ，以及支出所反映的市场价格（二价）。如果没有竞得，则不参与目标或约束的计算。ROI约束下竞价的目标是最大化收入总和，并且投产比 ROI 大于L，预算为B：

其中我们定义 为t次广告展现的拍卖信息序列。在下文，不引起歧义的前提下，我们采用缩写 。

最优出价定理二价拍卖机制下，如果所有拍卖都事先知道，即 都已知，可以推导出它的最优出价公式 （定理1）。证明请参考论文附录。

3.2 POCMDP建模

本文采用了强化学习的环境互动式学习的方式来学习竞价策略。训练阶段所使用的的拍卖环境基于高价桶日志数据集的经验分布构建。由于竞价策略需要实时的对每个广告展现报价。然而实际的广告系统中每天吞吐量可以达到数十亿。如果以单次请求为决策过程的一步，决策过程的序列长度过长而难以训练。如定理1所述，最优出价公式对于效用是线性的。因此本文将亿级别的长序列实时出价问题转化为时间片粒度的出价系数控制问题，并把市场发生相对显著变化的时间单位作为一个时间片的长度。至此，我们构建了以下的部分观测约束的 MDP（Partially Observable Constrained MDP），，其中：

• 状态 和观测 包含了时间片粒度的一些累积统计量，具体请参考论文附录。
• 动作 是每个时间片的出价系数（定理1中 ），有界正实数。
• 刻画环境的初始状态、转移和观测的发射概率。
• 奖励函数 和成本函数 用于刻画竞价问题的目标价值和约束破坏情况

基于示性函数设计的奖励函数

为了求解上述 POCMDP，我们注意到其约束形式具有等价的非约束形式，

其中我们定义了基于示性函数的奖励函数：

为简便地表示可行解和不可行解，定义： 表示 分别是满足 ROI 约束、预算约束和两个约束均满足的可行解， 代表它们的否定集合。

上述奖励函数的设计有以下特点：

• 等价性，是由于成立。

• 没有引入额外的超参数

• 满足贝尔曼方程的递归性质，即：

由此，对于上述约束的 MDP 的策略优化，我们可以基于该奖励函数采用任何基于贝尔曼方程的无约束 MDP 策略优化方法。这种基于示性函数的奖励函数设计对于约束条件的处理十分简洁，但十分有效的解决了过去工作的局限性。其背后的设计思想是在可行解和不可行解之间构建硬间隔，在奖励上单调地反映解的质量（默认可行解优于不可行解，而无关目标价值），避免引入额外参数再来控制约束和优化目标之间的权衡。因此，策略需要学会自适应调节约束和优化目标之间的权衡来获得更高的奖赏，而不是依赖于额外设置或优化出的固定超参数。

4. CBRL: 课程引导的贝叶斯强化学习框架

原则上，基于上述 POCMDP 建模已经可以进行策略优化，但是稀疏奖赏和不可观测性是悬而未决的两个挑战。为此我们提出了一个结合课程学习和贝叶斯学习的CBRL框架。

图2.方法概览图

本工作提出 CBRL 学习框架解决 ROI 约束下的竞价问题。智能体由一个课程序列引导，学会基于历史轨迹推断未观测的市场状态，并针对市场状态自适应地调节约束和目标价值之间的权衡。

4.1 课程引导的策略搜索

注意到上文设计的奖励函数 只在终止时刻提供奖赏信号。稀疏奖励往往导致策略探索的低效（例如离散有限动作空间的回合制 MDP 中 worst-case 探索需要指数时间），而且由于探索不到近优的状态动作分布而导致策略的次优性能。我们发现，利用约束竞价问题的约束结构，我们可以通过构造一系列结构近似且最优解接近的 proxy 问题作为先修课程，通过稠密奖励来引导策略在状态动作空间的探索。

具体地，定义以下形式的近似问题：

在原问题的终止时刻约束条件之外，在每个时间片额外增加了共 T-1 个约束条件。这个近似问题可以进一步推出贪心近似问题，在每个时间片的目标是最大化累积价值并满足累积约束：

而这种递归结构提供了一个稠密的奖励函数，对于满足截止到当前时间片累积约束且片内收入较大的动作有较高的奖励。

稠密的奖励函数提供了直接的引导信号来帮助缩小策略的探索空间（在离散有限动作空间的回合制MDP的情况下，worst-case探索仅需要多项式时间），但是问题的近似也导致解的欠优。为此，我们通过设计一系列终结于原始问题的课程来保证策略求解的最优性。

其中每个近似问题由增加的约束条件极限

所表征。原则上，约束条件极限的设计随着 k 增加而增加（靠前的课程约束强但是欠优程度也更强），随着时间逼近原问题的约束极限。具体课程设计请参考论文附录。

直观上，我们结合约束竞价问题的结构特性，通过引入课程学习将 worst-case 指数时间的探索效率提升到了多项式时间。在实验中我们发现，课程学习提升了超过五倍的收敛效率，同时能收敛到更优的解。

4.2 贝叶斯强化学习

在上述的 MDP 建模中，我们将环境的部分可知和非稳态变化都归结为 MDP 的部分观测性。而为了有效地处理这一点挑战，我们采用了贝叶斯视角，目标是通过变分贝叶斯学习近似推断不可观测部分的后验分布（即当前市场及其变化成因的后验），并基于后验采样自适应地决策、平衡约束和目标价值。

具体而言，我们采用隐变量 z 刻画不可观测的市场及其变化，目标学习基于历史轨迹 的后验分布 近似其真实分布。由于真实分布的未知或不可解，我们通常采用变分贝叶斯达到近似推断的目的。注意到在Q学习一类的强化学习方法中，Q 学习的目标是最小化贝尔曼残差，它等价于为转移元组 极大似然估计的目标：

由此我们可以推导出变分下界作为学习近似推断的目标函数，具体推导见论文附录。

基于上式，我们可以学习一个用于推断隐变量 z 后验的变分分布，它基于策略过去的历史轨迹推断当前未观测的市场情况。基于 Q 学习目标和最大化Q价值，我们学习出策略分布。在部署时，智能体 与近似推断 互相配合，通过后验采样在未知环境中进行决策。在后验采样过程中，首先从 采样 ，策略依据表征的信念 MDP（belief-MDP）执行动作 。新动作构造出新的转移元组，并加入到历史轨迹，用于更新后验分布 。这样的迭代过程在环境未知的情况下，呈现出贝叶斯最优（Bayes-Optimal）的探索利用权衡。

分析策略的优化目标，可以发现，在未知环境中，策略的决策选择的是环境不确定性期望下的最优动作，权衡了探索与利用。与此同时，Q 价值在我们的定义下始终保持了可行解和不可行解之间的硬间隔。因此，相比于过去依赖于额外设置超参数控制约束目标权衡的方法[3,7]，CBRL框架将要求策略学习依据推断的市场状态自适应调节约束目标权衡，以达到较高的Q价值。

5. 实验

我们在大规模工业数据构造的两个问题设定下进行了验证，回答了以下三个问题：1）CBRL方法与过去的方法的对比表现；2）所提出的课程学习的学习效率；3)所提出的贝叶斯学习在非稳态（甚至分布外）环境中的自适应控制能力。

5.1 综合性能

我们主要对比了三类能够（改编用于）处理约束竞价非单调性约束的方法，包括：1）对偶方法[4]；2）近似方法[5,6]；3）引入超参数的方法[7,3]。对于所有方法我们均进行20次随机试验绘制箱线图。其中，所提出的方法CBRL在约束满足和目标优化的综合表现上性能最优并且保持统计稳定性。其他具体分析请参考论文。

图3.与过去方法的对比。每个方法进行20次随机试验绘制出箱线图。黑线和红线分别代表中位数和均值

5.2 课程学习的学习效率

针对基于强化学习的方法，我们对比了[3]以及数个基线方法。其中，我们发现一个课程的学习下就可以达到接近收敛的性能，相比于直接优化原始问题，学习效率提高了超过五倍。

图4. 学习效率的对比。其中误差区间基于20次随机试验计算

5.3 贝叶斯强化学习的自适应控制

为了验证贝叶斯学习在动态调节约束与目标价值之间权衡上的作用，我们对比了基于强化学习的方法（详情参考论文图6），特别在分布外的测试场景上发现了贝叶斯学习的显著优势。具体而言，在存在系统变化和外部博弈的投放场景上，CBR在不同的随机试验中仍然保持基本满足 ROI 约束，同时保持一定的收入水平，其中位数约束满足率接近75%。对比之下，由于没有考虑环境的非稳态变化，过去的工作通常难以在分布外的测试场景权衡好约束与目标价值。

图5. 分布外测试场景下与USCB[3]的对比。横轴为问题实例ID，纵轴为regret。蓝色代表可行解，橙色代表不可行解。散点图和KDE分别反映联合分布和边缘分布

6. 总结与展望

本文针对非稳态市场下的ROI约束竞价问题提出了一种硬间隔处理约束的方法。该方法基于示性函数设计奖励函数，将约束问题转化为无约束问题求解，并开发了一个CBRL学习框架数据驱动地学习竞价策略。大规模的实验验证了所提出的方法在稳定性、学习效率、分布内外泛化能力上的优越表现。

该项工作对于通用场景下的约束竞价问题尚且只是一个初步尝试，仍然存在一些局限性。在方法论上，尽管课程学习能有效的提升学习效率，但是课程的设计仍然需要额外的基于数据的人工设计；在问题设定上，我们没有过多地探讨广告系统有偏采样和数据反馈（data feedback loop）问题，对于市场环境的非稳态变化和外部博弈的建模也只是浅尝辄止。这些都是非常有现实意义的问题，也欢迎感兴趣的同行follow我们的工作。

最后，欢迎感兴趣的同学加入我们。简历投递邮箱：

[e-mail]

参考文献

[1] Shuai Yuan, Jun Wang, and Xiaoxue Zhao. 2013. Real-time bidding for online advertising: measurement and analysis. In Proceedings of the seventh international workshop on data mining for online advertising. 1–8.

[2] S. Balseiro, A. Kim, M. Mahdian, and V. Mirrokni. 2021. Budget-Management Strategies in Repeated Auctions. Operations Research 69, 3 (2021).

[3] Yue He, Xiujun Chen, Di Wu, Junwei Pan, Qing Tan, Chuan Yu, Jian Xu, and Xiaoqiang Zhu. 2021. A Unified Solution to Constrained Bidding in Online Display Advertising. Association for Computing Machinery, New York, NY, USA, 2993–3001. https://doi.org/10.1145/3447548.3467199

[4] T. Wang, H. Yang, H. Yu, W. Zhou, and H. Song. 2019. A Revenue-Maximizing Bidding Strategy for Demand-Side Platforms. IEEE Access PP, 99 (2019), 1–1.

[5] Xun Yang, Yasong Li, Hao Wang, Di Wu, Qing Tan, Jian Xu, and Kun Gai. 2019. Bid optimization by multivariable control in display advertising. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1966–1974.

[6] Antoine Jamin and Anne Humeau-Heurtier. 2019. (Multiscale) Cross-Entropy Methods: A Review. Entropy 22 (12 2019). https://doi.org/10.3390/e22010045

[7] Chen Tessler, Daniel J Mankowitz, and Shie Mannor. 2018. Reward constrained policy optimization. arXiv preprint arXiv:1805.11074 (2018).

[8] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review (2007).

END

也许你还想看

喜欢要“分享”，好看要“点赞”哦ღ~

↓欢迎留言参与讨论↓