View on GitHub

memo

Application of bandit

バンディット手法の応用

10.1 モンテカルロ木探索

10.2 インターネット広告

PPCの場合は、広告配信会社はクリック率が高い広告を配信したい。 新しい広告については、クリック率のデータがないので、特徴量に対するクリック率の高い広告の探索とクリック率の高い広告の配信をバランスする必要がある。 この意味で、バンディット問題は有用であると考えられる。

広告配信で考慮されるべき要素としては

以上を考慮すると、 次の雑な線形計画問題を考えることができる。

\[\begin{align} \max_{x_{i, j}} & & & \sum_{i=1}^{L} \sum_{j=1}^{K} \rho_{i,j} x_{i, j} \nonumber \\ \mathrm{subject\ to} & & & \sum_{j=1}^{K} x_{i, j} = p_{i} \quad (i = 1, \ldots, L) \nonumber \\ & & & \sum_{i=1}^{L} x_{i, j} = d_{i} \quad (j = 1, \ldots, K) \nonumber \end{align}\]

制約の第一式は、配信回数がページのアクセス回数を超えないという制約である。 第二式は、配信回数が予算を超えないという制約である。 この線形計画問題に対して、\(\rho_{i, j}\)をバンディット手法によって推定するという手法が考えられる。 特に、ギッティンズ指標を用いて、配信回数が少ないことによる、推定精度の悪さを補う方法が提案されている。

次に、最近良く利用される広告オークション(advertising auction, ad auction)について考える。 ad auctionでは、各クリックに対して支払っても良い金額を各広告主が掲示し、あらかじめ決められた規準に基いて、掲示された広告の中から広告配信会社が配信する広告を決める。 つまり、各クリックごとに広告主がオークションの参加者となって、金額をbidするのである。 以下では、広告スペースは一つ固定して単純化して議論する。 この単純化は、広告スペースの閲覧者層によってクリック率が変わる広告主の立場から深刻であるが、応用上は広告配信会社の広告配信決定問題が中心的である為、ここではこれを認める。

以上の記号の下に、用語を定義する。

Definition. first-price auction

第1価格オークション(first price auction)とは、掲示金額が最も高い広告が配信され、掲示金額をそのまま支払う場合を言う。 つまり、

\[\begin{eqnarray} j(t) & = & \argmax_{j}b_{t, j} \nonumber \\ p_{t, j(t)} & = & \mathrm{max}_{j}b_{t, j} \nonumber \end{eqnarray}\]

である。

■

Definition. second-price auction

第2価格オークション(second price auction)とは、掲示金額が最も高い広告が配信され、2番目に高い掲示金額を支払い金額とする場合を言う。 つまり、

\[\begin{eqnarray} j(t) & = & \argmax_{j}b_{t, j} \nonumber \\ p_{t, j(t)} & = & \mathrm{smax}_{j}b_{t, j} \nonumber \end{eqnarray}\]

である。 但し、\(\mathrm{smax}_{j}\)は$j$で添字付けられた集合の中で2番目に大きい値である。

■

以下では、第二価格オークションの場合に限って話をすすめる。

以上の記号の下、広告$j$の(広告主に対する)効用\(U_{j}\)を以下で定義する。

\[\begin{eqnarray} \forall b_{i} \in \mathbb{R}_{\ge 0}, \ U_{j}(b_{1}, \ldots, b_{T}) & := & \sum_{t=1}^{T} \left( v_{t, j} c_{t, j} x_{t, j} - p_{t, j} \right) \nonumber \\ & = & \sum_{t=1}^{T} \left( v_{t, j} c_{t, j} - p_{t, j} \right) \label{def_utility} \end{eqnarray}\]

つまり、広告$j$が配信された時の効用と支払った金額との差である。 advertising auctionの設計とは、各$t = 1, \ldots, T$時点において以下の2つを決めることである。

  1. 以下を考慮して$t$で配信する広告$j(t)$を決定
    • 広告の掲示金額\(b_{t, j}\ (j = 1, \ldots, K)\)
    • 過去の配信広告$j(s) (s < t)$
    • クリックの履歴\(c_{s, j(s)}\ (s < t)\)
  2. クリックされた場合の請求金額\(p_{t, j(t)}\)の決め方の決定
    • 関数形の決定
    • 例えば、第二価格オークションなら2番目に高い掲示金額が請求金額

Remarks

$j(t)$が決まれば、\(x_{t, j}\)は完全に決まり、逆も同様である。 \(c_{t, j}\)は、配信の有無\(x_{t, j}\)とユーザに依存する。 ユーザなどの不確定性を確率的に考えれば、\(c_{t, j}\)は\(b_{t, j}\)に依存した確率変数と思える。 \(p_{t, j}\)は\(c_{t, j}\)と\(b_{t, j}\)に依存する(依存させることができる）。 \(c_{t, j}\)が確率変数と思えば、\(p_{t, j}\)も確率変数と思える。

■

広告代の合計の期待値を

\[\sum_{t=1}^{T} \sum_{j=1}^{K} \mathrm{E} \left[ P_{t, j} \right]\]

とする。 真のクリック率$\rho_{j}$がわかっていたとする。 つまり、$C_{j}$の真の分布がわかっていたとする。 この時の$t$での第二価格オークションの期待収益(expected revenue)は

\[\begin{equation} \rho_{j(t)} \mathrm{smax}_{j} b_{t, j} \label{def_expected_revenue} \end{equation}\]

である。 この期待収益と実際に請求する金額の期待値との差を$T$-Regretと定義する。 つまり、

\[\begin{eqnarray} T\mathrm{-Regret} & := & \sum_{t=1}^{T} \rho_{j(t)} \mathrm{smax}_{j} b_{t, j} - \sum_{t=1}^{T} \sum_{j=1}^{K} \mathrm{E} \left[ P_{t, j} \right] \label{def_t_regret} \end{eqnarray}\]

である。

以下では 必要な用語を定義しよう。

Definition. truthful auction for a click event sequence $C$

広告$j$以外の広告のbidの組全体を以下で定義する。

\[\begin{equation} B(j) := \left\{ (b_{1}, \ldots, b_{j-1}, b_{j+1}, \ldots, b_{t}) \in \mathbb{R}_{\ge 0}^{K-1} \right\} \nonumber \end{equation}\]

クリックの列$C$に対して正直なオークションとは、全ての広告$j$について、\(v_{j} = b_{t, j}\)でbidした時に、他の広告の掲示金額がいくらであろうと、$j$の効用が最大となることをいう。 つまり、

\[\begin{eqnarray} & & \forall t = 1, \ldots, T, \ \forall j = 1, \ldots, K, \nonumber \\ & & b_{t, j} = v_{t, j} \Rightarrow \forall (b_{1} ,\ldots, b_{K}) \in B(j), \ U_{j}(b_{1}, \ldots, b_{t, j}, \ldots, b_{T}) = \max_{b_{j} \in \mathbb{R}_{\ge 0}} U_{j}(b_{1}, \ldots, b_{j}, \ldots, b_{T}) \end{eqnarray}\]
■

Definition. always truthful auction

任意のクリック履歴について、正直なオークションを、常に正直なオークション(always truthful auction)という。 つまり、任意の\(\forall C \in \{0, 1\}^{K T}\)について、$C$に対して正直なオークションである。

■

次が成り立つ。

Proposition.

第2オークションは正直なオークションである。

proof.

$T=1$の時示せば十分であるから、$t$は省略する。 $\forall j = 1, \ldots, K$とし、\(\forall b_{j} \in \mathbb{R}_{\ge 0}\)とする。 第二オークションにおける効用は以下のようにかける。

\[\forall (b_{1} ,\ldots, b_{T}) \in B(j), \ U_{j}(b_{1}, \ldots, b_{j}, \ldots, b_{T}) = \begin{cases} v_{j}c_{j} - c_{j}\max_{j \neq j^{\prime} \neq}b_{j^{\prime}} & b_{j} > \max_{j \neq j^{\prime}}b_{j^{\prime}} \\ 0 & \mathrm{otherwise} \end{cases}\]

$b_{j} = v_{j}$とし、以下を示せば良い。

\[\begin{eqnarray} \forall (b_{1} ,\ldots, b_{T}) \in B(j), \ U_{j}(b_{1}, \ldots, b_{j}, \ldots, b_{T}) = \max_{b \in \mathbb{R}_{\ge 0}} U_{j}(b_{1}, \ldots, b, \ldots, b_{T}) \nonumber \end{eqnarray}\]

\(\forall (b_{1} ,\ldots, b_{T}) \in B(j)\)として固定する。

まず\(b_{j} > \max_{j \neq j^{\prime}}b_{j^{\prime}}\)の場合は、

\[c_{j}(b_{j} - \max_{j \neq j^{\prime}}b_{j^{\prime}})\]

であり、$b$によらないので、成り立つ。 同様に\(b_{j} \le \max_{j \neq j^{\prime}}b_{j^{\prime}}\)の場合は恒等的に0なので、これも$b$によらず成り立つ。 \(\forall (b_{1} ,\ldots, b_{T}) \in B(j)\)であったから、主張は成り立つ。

$\Box$

以上の準備のもと、次のアルゴリズムを考える。

Algorithms 10.2 正直なオークション型広告配信設計

大きく3つに別れる。 最初に、$K$個の広告を約$\tau / K$回ずつ掲載して、クリック率に関する推定値を算出するためのクリック履歴を得る。 次に、得られたクリック履歴からクリック率の推定を行う。 最後に、推定値の良いものを配信する。

\[\begin{eqnarray} \hat{\rho}_{j} & := & \sum_{t=1}^{K \lfloor \tau / K \rfloor} \frac{ c_{t, j} }{ \lfloor \frac{ \tau }{ K } \rfloor }, \nonumber \\ \hat{\rho}_{j}^{+} & := & \hat{\rho}_{j} + \sqrt{ 2 \frac{ \left( \log \frac{K}{\delta} \right) }{ \lfloor \frac{\tau}{K} \rfloor } } \nonumber \end{eqnarray}\]
■

このアルゴリズムの$T$-Regretの上界は以下で与えられる。

Thereom 10.1

Alogrithm 10.2において、

ととれば、

\[T\mathrm{-Regret} = O(b_{max}K^{1/3}T^{2/3}\sqrt{\log KT})\]

となる。 ただし、\(b_{max} := \max_{j, t}b_{t, j}\)である。

proof.

$\Box$

Memo

以下のモデルを考えていると思って良さそう。

ややこしいのは、$C_{j}$はあくまで、配信された場合のクリック率であるということ。 その為、\(c_{j, t} := C_{j, t}(\omega)\)ではない。

論文と本では、\(\eqref{def_expected_revenue}\)は、クリック率がsmaxの中に入ったものを、expected revenueと定義しているが、second price auctionの場合は、クリックの有無は配信広告のクリック率で決まるので、外に出すのが妥当と思う。 そうだとすると、論文の主張と結果も正しいかは確認が必要。

Reference

10.3 推薦システム