予算消化制御のための入札率のfeedback制御

はじめに

こんにちは. マイクロアドで機械学習エンジニアをしている福島です. 主にReal-Time-Bidding (RTB)におけるClick Through Rate/Conversion Rate(CTR/CVR)予測や入札最適化の研究・開発を担当しています. 現在マイクロアドでは, UNIVERSE Adsというプロダクトで予算配分制御のための入札率のfeedback制御を導入しています.

今回は, 入札率のfeedback制御について紹介します.

はじめに
RTBにおける予算管理
- 入札率のfeedback制御
- 目標消化金額の計算
導入結果
終わりに

RTBにおける予算管理

RTBでは下図のように, 広告主とメディア間でリアルタイムにオークションが開催され, オークションに勝利したDemand Side Platform (DSP)がコストを支払い広告を表示する権利を獲得します.

f:id:fukushima-08:20220317170106p:plain — RTBの仕組み

DSPの目的としては, 広告効果の改善やスムーズな予算消化が挙げられます. 一般的には広告キャンペーンに対し日予算が設定されており, 日予算を超えないように配信が行われています.

マイクロアドでは一日の前半で予算を消化し切ってしまうことを防ぐために, [Kuang-Chih Lee, et al., 2013]による入札率のfeedback制御を導入しています.

入札率を制御し, 予算を一日を通して消化することの利点として次のようなことが考えられます.

様々な層へ広告をリーチすることが可能
- 多様性の高い配信ログとなることで, CTR/CVR予測などの学習データの質も向上
後半の効果の高いリクエストに備えることが可能 (機会損失の削減)
入札候補が減ることによる配信負荷の軽減

入札率のfeedback制御

1日を $T$ 個のタイムスロットに分割した時, タイムスロット $t$ での消費コスト $s(t)$ はそのタイムスロットでのインプレッション数 ${\rm imp}(t)$ に比例します.

$s(t) \propto {\rm imp}(t)$

消費コストと入札率の関係を考えるために, タイムスロット $t$ でのインプレッション数を以下のように式変形します.

${\rm imp}(t) = {\rm reqs}(t) \frac{{\rm bids}(t)}{{\rm reqs}(t)} \frac{{\rm imps}(t)}{\rm{bids}(t)}$

ここで, ${\rm reqs}(t)$ と ${\rm bids}(t)$ はそれぞれタイムスロット $t$ におけるリクエスト数と入札数です. このとき, $\frac{{\rm bids}(t)}{{\rm reqs}(t)}$ と $\frac{{\rm imps}(t)}{\rm{bids}(t)}$ はそれぞれ入札率と落札率を表します.

以上より, タイムスロット $t$ での入札率と落札率をそれぞれ $\text{pacing_rate}(t)$ と $\text{win_rate}(t)$ としたとき, 次の関係か成り立ちます.

$s(t) \propto {\rm reqs}(t) \cdot \text{pacing_rate}(t) \cdot \text{win_rate}(t)$

上記の入札率と消費コストの関係から, タイムスロット $t+1$ での目標消化金額 $b_{t+1}$ を達成するための入札率 $\text{pacing_rate}(t + 1)$ は再帰的に計算できます.

$\begin{aligned} \text{pacing_rate}(t + 1) &= \text{pacing_rate}(t) \frac{s(t + 1)}{s(t)} \frac{\text{reqs}(t)}{\text{reqs}(t + 1)} \frac{\text{win_rate}(t + 1)}{\text{win_rate}(t)} \\ &= \text{pacing_rate}(t) \frac{b_{t + 1}}{s(t)} \frac{\text{reqs}(t)}{\text{reqs}(t + 1)} \frac{\text{win_rate}(t + 1)}{\text{win_rate}(t)} \end{aligned}$

このとき, タイムスロット $t + 1$ でのリクエスト数 $\text{reqs}(t + 1)$ と落札率 $\text{win_rate}(t + 1)$ は未知の値です. ただし, ここで必要なのはリクエスト数と落札率のタイムスロット $t$ から $t+1$ における変化率なので, 過去の配信実績から容易に推定可能です.

目標消化金額の計算

入札率の計算ができたところで, タイムスロット $t+1$ での目標消化金額をどのように設定するべきかという問題が残ります.

シンプルに考えると, 残りの日予算をタイムスロットの数で分割した値を設定することでflatなペーシングを行うことが可能ですが, 次のように推定リクエスト数に応じた配分も可能です.

$b_{t + 1} = (B - \sum_{m = 1} ^ t s(m)) \frac{p_{t+1} \text{reqs}(t+1)}{ \sum_{m=t+1}^T p_m \text{reqs}(m)}$

ここで, $B$ は広告キャンペーンの日予算, $\text{reqs}(t)$ はタイムスロット $t$ における, 対象の広告キャンペーンのターゲティング設定に対する推定リクエスト数です.

また, 効果改善のための予算配分方法を組み込むことも可能です.
例えば, 次のように目標消化金額 $b_{t+1}$ を計算する方法が考えられます.

$b_{t + 1} = (B - \sum_{m = 1} ^ t s(m)) \frac{p_{t+1} L(t+1)}{ \sum_{m=t+1}^T p_m L(m)}$

ここで, $L(t)$ はタイムストロット $t$ の長さ, $p_{t}$ はタイムストロット $t$ におけるクリックの確率密度関数です.

上記のように予算を配分することで, クリックのされやすい時間に予算を多めに配分できます.

このように, 任意の予算配分方法によって計算した目標消化金額を達成するための入札率の計算が可能です.

現在マイクロアドでは, スムーズな予算消化を優先し, 残り予算を想定リクエスト数に応じて分配しています.

導入結果

ある広告キャンペーンに対し, 入札率の初期値を0.3として1時間ごとにfeedback制御を適用( $T=24$ )し, 入札率を再計算して配信した結果が以下になります.

f:id:fukushima-08:20220318150534p:plain — feedback制御導入結果. (上)累積消化金額 (下)入札率推移

想定どおり, 23時台で予算を消化し切ることができています.
また, 翌日の入札率の初期値に関しては, 前日の最後から2番目の入札率を引き継ぐようにしています. (最後の入札率はブレが大きいため)

終わりに

今回は, 入札率を制御する形の予算消費制御を導入しました.
消化金額の制御方法に関しては, [Santiago Balseiro, et al., 2017]にもまとめられていますが, 入札率の制御以外にも入札金額の制御する方法なども考えられます. 手法ごとにメリットやデメリットが存在しますが, 予算消費管理は広告効果とも関連が深いため, 今後も調査・改善を続けていきます.

機械学習エンジニア絶賛採用中

マイクロアドでは, 問題設定からサーベイ, 開発・運用まで裁量を持ってチャレンジしたいという仲間を募集しています！また, 機械学習エンジニアだけでなく, サーバサイド, フロント, インフラエンジニアなど幅広く募集しています！
気になった方は以下からご応募ください！ recruit.microad.co.jp

参考文献
Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising, Kuang-Chih Lee, et al., ADKDD2013

Budget Management Strategies in Repeated Auctions, Santiago Balseiro, et al., WWW2017