検索
検索をクリア
検索終了
Google アプリ
メインメニュー
true

概要

付録(多腕バンディット)

計算と理論の詳細

まず、「多腕バンディット」は、複数の解法が提唱されている問題であるという点を念頭に置いてください。「強化学習」に関する書籍を開くと、多腕バンディットに関する導入部にさまざまな解法が記載されているはずです。多腕バンディット問題の背後にある数学は非常に難解なため、発見的な解法が使用されているいうことが、その理由です。数学的な難解さは、Peter Whittle(1979 年)の次の言葉に要約されています。

[バンディット問題] は [第 2 次世界] 大戦中に定式化されたが、連合国側のアナリストがそれを解くための研究でエネルギーと頭脳を大幅に消耗させられることとなったため、この問題は知的破壊兵器としてドイツに投下するべきだという案も提出されることとなった。

アナリティクスでは、トンプソン検定やランダム確率一致といった発見的手法を採用しています。この手法には、これらの発見的手法の最も優れた点の多くが組み込まれているためです。この手法の詳細については、[5] をご覧ください。数学的な特質については、[2]、[3]、[4] で確認できます。

最適なページである確率

トンプソン検定では、各ページが最適な設定である確率と比例する形で、ページにセッション数を振り分けます。これはベイズ式の計算です。θ =(θ1, θ2,..., θk)を、ページ 1, …, k のコンバージョン率のベクターとします。y をテストにおける観測対象データとします。y を独立した 2 項式の解としてモデル化し、θ の一様事前分布とみなします。Iaθ)をページ a が最適であるというイベントのインジケータとすると、次の数式が導出されます。

P(Ia)= ∫Ia(θ)p(θ|y)dθ

この積分は、閉形式(ただし、閉形式の求解には、不完全ベータ関数などの複雑な特殊関数が関わってきます)または数値積分法によって実行できます。どちらの場合でも、この計算は y の値が比較的小さくても早い段階で安定しなくなります。しかし、最適なページである確率は、シミュレーションによって安定的に計算できます。θ の各要素はベータ分布から独立したランダム変数です。関連するベータ分布からの θ の抽出で構成される大規模な行列をシミュレーションします。この行列の行はランダム抽出となり、列はテスト対象となる k 個のページとなります。ページ a が最適である確率のモンテカルロ推定は、ページ a が最大のシミュレーション値を持つ行の経験的割合となります。各パターンがオリジナルより優れている確率は、同様に計算されます。

残存価値

最適なページである確率を導出するシミュレーションでは、テストの残存価値の分布も算出されます。残存価値は、(θmax-θ*)/θ* の事後分布となります(θmaxθ の最大値、θ* は最適である確率が最も高いページの θ の値です)。計算例として、それぞれセッション数が 20、30、40 回で、コンバージョン数が 12、20、30 回の 3 つのページがある場合を見ていきます。最適なページである確率は、概算で 9%、20%、71% となります。θ のモンテカルロ シミュレーションからの最初の 6 件の抽出結果は、次のようになります。

[,1] [,2] [,3]
[1,] 0.54 0.73 0.74
[2,] 0.55 0.66 0.73
[3,] 0.53 0.81 0.80
[4,] 0.57 0.50 0.65
[5,] 0.52 0.67 0.83
[6,] 0.65 0.84 0.63

行ごとに、列 3 の要素(ページ 3 が最適である確率が最も高いため)からその行の最大要素を引く形で値を算出します。最初の 2 行では、列 3 の値が最も大きいため、kの値はゼロとなります。3 行目では、2 列目が 3 列目よりも 0.01 大きいため、この値は 0.01/0.80 となります。各行でこのような計算を行うと、値の分布が得られ、それを基に図 A1 の左側の画像のようなグラフを作成できます。ページ 3 は最適なページである確率が 71% であるため、3 以外のページを選んだ場合ことの価値は、71% の確率でゼロとなります。値の分布の 95 パーセンタイル値がテストにおける「残存潜在価値」となり、このケースではおよそ 0.16 と導出されます。この数値は、「ページ 3 のコンバージョン率については確証が得られていないが、そのコンバージョン率にかかわらず、その他のページのいずれかがページ 3 より 16% 優れている可能性がある」という意味になります。

図 A1 の右側の画像は、テストの進行とともに残存価値の分布がどう変容していくのかを示した図です。各ページのセッション数が 5 倍になってそれぞれ 100、150、200 回となり、コンバージョン数も 5 倍になって 60、100、150 回になったとします。サンプル数が増加したことで、各ページのコンバージョン率の確度が高まっています。ページ 3 が最適なページである確率が 95% に達したため、残存価値の分布の 95 パーセンタイル値はゼロになりました。

図 A1: テストにおける残存価値の分布。縦軸が 95 パーセンタイル値、つまり残存潜在価値です。
この記事は役に立ちましたか?
改善できる点がありましたらお聞かせください。