The First Cry of Atom Today is the first day of the rest of my life.

An efficient bandit algorithm for real-time multivariate optimization

KDD ‘17で、Audience Appreciation Awardにも選ばれていた”An efficient bandit algorithm for real-time multivariate optimization”という論文を読みました。

Amazonがコンバージョンを上げるためにいわゆるA/Bテストをいかに効率よく行うかという問題をMulti-armed banditの手法で解いたというものです。例えばあるECサイトのウェブページがあったとします。 このページにはコンポーネント5つあり、それぞれ取りうるパターンが決まっています。ボタンは赤か青、画像は3パターンが用意されているといった具合に。この時すべてのパターンをテストするには48パターン(=2☓2☓3☓2☓2)を試す必要がありますが、更にそれぞれのパターンの妥当なテストボリュームを考えると、Amazonのトラフィックサイズでもこのテストには全部で66日程度かかるそうです。

widget

コンポーネントが増えると、組み合わせが爆発してしまうのでこのパターンを抑える必要があります。このためのモデルをまず考えてみましょう。

モデル

簡単のためレイアウト上のコンポーネントのパターンはすべて同じとします。つまり、番目のコンポーネントのパターンをとすると

\begin{equation} N_1 = N_2 = … = N \end{equation}

となります。そしてD個のコンポーネントがあるとすると組み合わせのパターンは全部でとなります。番目のコンポーネントのパターンをと表すとするとレイアウトは として表現することができます。

モデルに対する報酬(Reward)を決めるのはレイアウトだけではありません。ユーザの属性や時間、場所などのセッション情報からも決まります。同じレイアウトでも人によって何を買うか違いますしね。これをコンテキスト, として表現します。この時与えられる特徴は次元ベクトルで表されます。時刻tにおいて選ばれるレイアウトを、モデルのパラメタをとするとRewardの期待値は

\begin{equation} \mathbb{E} [R|A,X] = g(B_{A_t,X}^TW) \end{equation}

となります。は何らかの滑らかなリンク関数です。この時次のレイアウト

\begin{equation} A_{*} = argmax E[R_A,X_t] \end{equation}

を満たすものが選ばれますが、Multi-armed banditでは将来に渡っての報酬も増やさなければいません。これは以下のように定式化できます。

\begin{equation} \Delta_{t} = E[R_{A_*},X_t] - E[R_A,X_t] \end{equation}

を同時に最小にすることを求められます。これをRegretといいます。「あー、あっちを選んでおけばよかった」という感覚でしょうか。一般にはの下界はとなることが知られています。

ではどのように最適なを求めたらよいでしょうか。ここでは計算量を抑えるためにpair-wiseな特徴だけ考慮することにします。つまり各コンポーネントのRewardへのインパクトと各2コンポーネント間の関係のみを考慮します。 3つ以上は考慮しないことで計算量を抑えます。

\begin{equation} B_{A,X}^T W = W^0 + \sum_{i=1}^D W_i(A) + \sum_{j=1}^D \sum_{k=j+1}^D W_{j,k} (A) + \sum_{l=1}^L W_l^c (X) + \sum_{m=1}^D \sum_{n=1}^L W_{m,n}^c (A,X) \end{equation}

このモデルを使って学習を行う部分は以下のようにThompson Samplingというアルゴリズムを用います。Thompson SamplingはMulti-armed banditの問題を解くために古くから使われるもので(考案されたのは1933年とも)、期待報酬を最大にするようなレイアウトを選んでいきます。

Thompson Sampling

得られた報酬の履歴から事後分布を計算していきますが、ここでもやはりの計算量が問題になります。取りうるレイアウトのパターンはあるからです。

山登り法(Hill Climbing)

この論文では山登り法を使って最大報酬期待値を得るレイアウトを推定します。下表にあるようにいくつかのパターンに対してK回ランダムにコンポーネントを選択し、このコンポーネントのみを変更したとき最大報酬を与えるようなレイアウトを返します。これを様々な初期値で行い最終的に最も期待報酬の高いレイアウトを返します。計算量はとずっと小さくなることがわかります。

hill climbing

評価

evaluation

評価では上記5つの手法を比較していました。MVT*というのが提案されている方法でが従来手法です。下図はiteration毎のregretの値です。MVT1, MVT2の方が比較的速く収束していることがわかります。

local regret

下記はN = 8, D = 3でも山登り法の評価ですが、K=5程度でregretの値は収束することがわかります。

hill climbing eval

Recap

この手法が個人的に面白いと思った点は

特に2つめはこの手法でExploration-Exploitationのバランスをとりつつ、効果のでなさそうなレイアウトを先に排除しておくことでより洗練されたデザイン、レイアウトに時間を使うことができるかもと思いました。

Reference