AD-TECH
Lab BLOG
アドテクLab ブログ

NEWS
  • リクルートデータ組織のブログをはじめました。※最新情報はRecruit Data Blogをご覧ください。

多腕バンディット問題とA/Bテスト (Part 1)

2019/03/14kano_hideaki

このエントリーをはてなブックマークに追加

みなさん、こんにちは。ギャンブラー🤡の鹿野です。 今回は、機械学習の分野で注目を集めている多腕バンディット問題の中でも、 特にWebサイト最適化の文脈でしばしば出てくる確率的多腕バンディット問題 (stochastic multi-armed bandit problem) の基本的な枠組みとそれを解くアルゴリズムについて解説いたします (簡単のため、以下では「確率的多腕バンディット問題」を単に「多腕バンディット問題」と表記します) 。 本記事を読み終わったあとには

  • 多腕バンディット問題の基本的な枠組みとそれを解くアルゴリズム
  • Webサイト最適化においてどのように役に立つのか
  • A/Bテストと多腕バンディット問題の関係

について理解ができることを目標としています!

Part 1の本記事では古典的な多腕バンディット問題について、 Part 2ではより実践的な最近の多腕バンディット問題について解説することを予定しています。

本記事の動機

私は、去年まで大学院と研究所で多腕バンディット問題に関する研究をしていて、現在はバンディットアルゴリズムを活用したプロジェクトを進めているので、 これに関連する記事を読むことが多いです。しかし、特定の枠組みや実装に特化した記事は多いものの、 多腕バンディット問題とは何か?という基礎から出発し、様々な枠組みをその定式化とともに解説している記事は (ググり力が低いだけかもしれませんが) あまり見かけません。 この経験が本記事を書く動機です。本記事が多腕バンディット問題を理解するときの一助となれば幸いです。

多腕バンディット問題

多腕バンディット問題とは、 単独のギャンブラーが報酬の確率分布が未知の複数台のスロットマシンを繰り返しプレイするときに、どのような方策 (policy) に従うのがベストなのかを考える問題です。 もちろん、何がベストな方策なのかは目的によって異なるので、目的に応じて様々な枠組みが存在します。 (ちなみに、多腕バンディット問題という名前は、スロットマシンをギャンブラーからお金を奪う “1本腕の盗賊 (one-armed bandit)” と喩える遊び心に由来しています。 また、スロットマシンのことを単に “アーム” 、スロットマシンをプレイすることを “アームを引く” と呼ぶことが多いので、以下ではそれに倣います)。 最も基本的な枠組みは以下の2つです。

  • 累積報酬最大化 (cumulative reward maximization):
    ある時刻 $T$ までにギャンブラーが得る報酬の最大化を目指す枠組みで、 報酬に関して探索と活用のジレンマ (exploration-exploitation dilemma) が発生するのが特徴です。ここで、探索は報酬の期待値がより高いアームを探すことを意味し、 活用は経験平均 (empirical mean) が最も高いアームを引くことを意味しています。この枠組みは累積リグレット最小化 (cumulative regret minimization) とも呼ばれます。

  • 最適腕識別 (best arm identification):
    報酬の期待値が最大であるスロットマシンを探す枠組みで、探索途中の報酬は気にしない純粋探索問題 (pure-exploration problem) であることが特徴です。 以下の2つの設定があります。

    • 固定信頼度 (fixed confidence): 誤り確率 $\delta$ 以下で、報酬の期待値が最大であるアームを見つけるためのプレイ回数の最小化を目指す設定。
    • 固定予算 (fixed budget): 固定予算 (プレイ回数) $\mathrm{B}$ で、報酬の期待値が最大であるアームを探すときの誤り確率の最小化を目指す設定。

※文脈によっては累積報酬最大化の枠組みだけを多腕バンディット問題と呼んでいますが、 本記事では、引いたアームについてしか情報が得られないという状況の問題を多腕バンディット問題と呼んでおり、 最適腕識別も多腕バンディット問題に含まれるという広義の立場を採用しています。

累積報酬最大化の定式化と主なアルゴリズム

まず、累積報酬最大化の定式化について紹介します。 次に、この問題を解く主なアルゴリズムについて紹介いたします。

定式化 (累積報酬最大化)

$1$ 人のギャンブラーが $K$ 本のアームから $1$ つ選んで引くことを繰り返す場面を考えます。 それぞれのアーム $a \in [K] = \{1, 2, …, K\}$ は、期待報酬が $\mu_a$ である確率分布 $\nu_a$ を持つとします。 ただし、期待報酬 $\{\mu_a\} _{a=1}^K$ はギャンブラーには未知のパラメータです。 ギャンブラーは時刻 $t = 1, 2, …, T$ でアーム $a(t)$ を引き、 報酬 $X _{a(t)}(t) \overset{i.i.d.}{\operatorname{\sim}} \nu _{a(t)}$ を受け取ります。 このとき、累積報酬最大化は以下の期待リグレット $\mathbb{E} [ \mathrm{regret}(T)]$ の最小化として表すことができるので、この問題は $$ \mathrm{Minimize} \ \ \ \mathbb{E}[\mathrm{regret}(T)] = \mathbb{E} \left[ \max _{a \in [K ]} \sum _{t=1}^T X_a(t) - \sum _{t=1}^T X _{a(t)}(t) \right] $$ と書くことができます。

この期待リグレットの下界 (理論限界) は $\mathrm{O}(\log T)$ であることが知られています。

アルゴリズム (累積報酬最大化)

累積報酬最大化を効率良く解くアルゴリズムとして、以下のアルゴリズムが知られています。

  • Upper Confidence Bound (UCB) アルゴリズム:
    時刻 $t = 1, 2, …, T$ で ヘフディング (Hoeffding) の不等式に基づいて各アームの信頼区間の上限を計算し、その値が最も大きいアームを引くアルゴリズム。擬似コードは以下の通り。 ucb_pseudo_code

  • Thompson Sampling アルゴリズム:
    それぞれのアームに対して期待値が最大である事後確率を「計算」し、その事後確率が最大となるアームを引くアルゴリズム。ここで、「計算」と表記したのは、 この事後確率の計算は一般に困難なので、 事後分布に従って生成した乱数をこの事後確率の代わりとして用いるからです。 これによって、実際に計算困難な事後確率を計算せずに、 事後確率が最大となるようなアームを引くことができます。 報酬確率の分布をベルヌーイ分布とし、 この分布の共役事前分布 $\mathrm{Beta}(\alpha, \beta)$ を用いる場合の疑似コードは以下の通り。 thompson_sampling

これらのアルゴリズムによって得られる期待リグレットの上界のオーダーは、 理論限界のオーダーと一致することが知られています。

最適腕識別の定式化と主なアルゴリズム

まず、固定信頼度の定式化とそのアルゴリズムについて紹介します。 次に、固定予算の定式化を紹介します。

定式化 (固定信頼度における最適腕識別)

$1$ 人のギャンブラーが $K$ 本のアームから $1$ つ選んで引くことを繰り返す場面を考えます。 それぞれのアーム $a \in [K] = \{1, 2, …, K\}$ は、期待報酬が $\mu_a$ である確率分布 $\nu_a$ を持ち、 許容誤識別率 (acceptance error rate) を $\delta > 0$ とします。 ただし、期待報酬 $\{\mu_a\} _{a=1}^K$ はギャンブラーには未知のパラメータです。 ギャンブラーは、時刻 $t = 1, 2, …$ でアーム $a(t)$ を引き、 報酬 $X _{a(t)}(t) \overset{i.i.d.}{\operatorname{\sim}} \nu _{a(t)}$ を受け取ります。 そして、最適腕としてアーム $\hat{a}^* \in [K]$ を出力して停止するまでこのプロセスを繰り返します。 このとき、停止時刻を $\tau _\mathrm{stop}$ とすると、 固定信頼度における最適腕識別の問題は、停止時刻の期待値 $\mathbb{E}[\tau _\mathrm{stop}]$ の最小化として表すことができるので、

$$ \mathrm{Minimize} \ \ \ \mathbb{E}[\tau _\mathrm{stop}] \ \ \mathrm{subject \ to} \ \ \mathbb{P}[\hat{a}^* \neq a^*] \leq \delta \ , \ \mathrm{where} \ a^* = \underset{a \in [K]}{\operatorname{arg max}} \mu_a $$

と書くことができます。

この期待停止時刻の理論限界は $\mathrm{O}(\log 1/\delta)$ であることが知られています。

アルゴリズム (固定信頼度における最適腕識別)

  • Lower and Upper Confidence Bound (LUCB) Algoritihm:
    各アームに対してアームの信頼区間の上限と下限を計算し、 最も経験平均が高いアームの信頼区間の下限とそれ以外のアームの信頼区間の上限の差がなるべく早く広がるようにアームを引くアルゴリズム。 擬似コードは以下の通り。 lucb_pseudo_code

このアルゴリズムによって得られる期待停止時刻の上界のオーダーは、 理論限界のオーダーと一致することが知られています。

定式化 (固定予算における最適腕識別)

$1$ 人のギャンブラーが $K$ 本のアームから $1$ つ選んで引くことを繰り返す場面を考えます。 それぞれのアーム $a \in [K] = \{1, 2, …, K\}$ は、期待報酬 $\mu_a$ である確率分布 $\nu_a$ を持ち、 固定予算 (アームを引ける回数) を $B$ とします。 ただし、期待報酬 $\{\mu_a\} _{a=1}^K$ はギャンブラーには未知のパラメータです。 ギャンブラーは、時刻 $t = 1, 2, …, B$ でアーム $a(t)$ を引き、 報酬 $X _{a(t)}(t) \overset{i.i.d.}{\operatorname{\sim}} \nu _{a(t)}$ を受け取ります。 そして、時刻 $t = B$ で最適腕としてアーム $\hat{a}^* \in [K]$ を出力して停止するまでこのプロセスを繰り返します。 このとき、固定予算における最適腕識別の問題は、時刻 $t = B$ での誤り確率の最小化として表すことができるので、

$$ \mathrm{Minimize} \ \ \ \mathbb{P} [ \hat{a}^* \neq a^* ] \ , \ \mathrm{where} \ a^* = \underset{a \in [K]}{\operatorname{arg max}} \mu_a $$

と書くことができます。

この誤り確率の理論限界は、 $\mathrm{O} (\mathrm{e} ^{-bB})$ であることが知られています。 ここで、 $b$ は信頼区間の幅に関連するパラメータで、詳しくはGabillon et al., 2012を参照してください。

アルゴリズム (固定予算における最適腕識別)

固定予算の設定では、素朴 (アームの選択回数が固定/等頻度) でないアルゴリズムの理論については明らかになっていないことが多いので、割愛いたします。

なぜWebサイト最適化に役に立つのか

さて、いったいどのようにして効率的にスロットマシンをプレイする戦略がWebサイト最適化に役に立つのでしょうか? 多くのWebサイトの目的は、ユーザに対して広告や商品・サービスを配信・推薦し、閲覧/購入/予約をしていただくことです (Webマーケティングの用語では、閲覧/購入/予約などの成果を表すものを conversion または CVと呼ぶことが多いので、以下ではそれに倣います)。 ここで、ユーザに提供する広告/商品/サービスをスロットマシンに見立て、ユーザのCVを報酬と考えると、 ユーザに広告等を配信しより多くのCV数を獲得する問題や、CVに至る可能性が最も大きい広告を探す問題は、 累積報酬最大化や最適腕識別などの基本的な多腕バンディット問題として考えることができます。

もちろん、直接そのまま扱えるケースはあまり多くなく、 実際には理論と現実のはざまを埋めるために様々な工夫を凝らすことになります。 例えば、上で紹介した多腕バンディット問題の枠組みは、スロットマシンの報酬確率の分布は時間などで変化しないものでしたが、 conversion rate (CVR) は、時期や配信するエリアによって異なることが多かったり、画面上に表示される位置に影響を受けたりします。 しかしながら、このような困難な状況下であっても機能するようなバンディットアルゴリズムを考え実装するのは、エンジニアの腕の見せ場であり、やりがいのある楽しいところです!

A/Bテストとの関係

Webサイト最適化の手法としてよく知られているA/Bテスト (A/B testing) は、 アームの数が2つの場合の最適腕識別とみなすことができます。 したがって、時期や配信エリアによってCVRが異なるといった多腕バンディット問題で生じる問題は、A/Bテストでも同様に生じます。

また、A/B/nテスト (A/B/n testing) としてnコのパターンを試す際は、 広く用いられているA/Bテストと同様にA, B, …, nをすべて等頻度で試すのではなく、 最適腕識別のアルゴリズムを用いて効果の見込みが薄い候補を試す頻度を下げる方が、 より効率的に最適な広告やクリエイティブ (Web広告に用いる画像などの素材) を探索することができます。

参考資料

日本語の資料

英語の資料

広告

RCOアドテク部ではスロットマシン🎰と報酬💰が好きな優秀なエンジニアを募集しています。 こちらからご応募ください。お待ちしております!