バンディットアルゴリズムを勉強する機会があり、いくつかの本を読み、実戦で試すケースがありましたので、バンディットアルゴリズムによる最適化手法の使いどころについて、まとめてみました。
バンディットアルゴリズムとは
バンディットアルゴリズムは、A/Bテストのような一択を決めるためのテスト手法ではなく、新しいアイデアの探索と既存のロジックから最大限の利益を引きだすためのテスト手法と言われています。A/Bテスト同様にデータに基づいた意思決定手法です。
有名どころだと、下記の本が少し古いですが、勉強になりました。
https://www.oreilly.co.jp/books/9784873116273/
こちらの本は、バンディットアルゴリズムに関する基本的な知識について、ひと通り学ぶことができるのと、多腕バンディット問題についての資料を自力で読めるようになるところまで、網羅していました。
A/Bテストとは
A/Bテストとは何か
バンディットアルゴリズムをまとめているサイトだと、よく比較する例として、A/Bテストが挙げられています。A/Bテストとは、テストをしたい異なるUI/UXのサイトを数種類用意して、ユーザの使い方の違いをそれぞれのテストケースで調べるテストのことを指しています。同じ目的のページを用意した上で、ユーザに実際に使ってもらいながら、どっちが購入が多かったか、どっちがアクセス数が良かったかなど、目標にするKPIに沿って、効果検証をします。
A/Bテストで困ること
A/Bテストで困ることは、大きく2つあります。
・全アクセスをテストに使うことになる。
・テスト後に状況が変わっても最適化出来ない。
この2つが挙げられると思います。A/Bテストでは、実際に動いている全てのアクセスをテストとして、扱うことになりますし、何かしら外的要因で状況が変わった場合に、テスト後に最適化できないこともデメリットになると考えられています。そこでこのデメリットを解消するために使われるのが、バンディットアルゴリズムです。
バンディットアルゴリズムを検証する
A/Bテストのデメリットをどう解消できるか
先ほど、
・全アクセスをテストに使うことになる。
・テスト後に状況が変わっても最適化出来ない。
A/Bテストのデメリットを2つ挙げましたが、バンディットアルゴリズムではどう解消できるか説明したいと思います。
まず、全アクセスをテストに使うことになる。という点については、
効果が高いものを見つけるためのテスト(探索)と見つかった効果が高いもので実際に結果を得ること(活用)を割合配分して同時に行なうため、利益を最大化するためのロジックになっており、リスクをヘッジできる特徴があります。
さらに、 テスト後に状況が変わっても最適化出来ない。という点については、
探索と活用に分けることで、活用をしながらも常に探索が行い、状況変化に応じて活用に用いるものを変えていくテスト手法になるので、状況の変化に柔軟に対応していくことが可能です。
Epsilon-Greedy アルゴリズム
バンディットアルゴリズムの中で、最も単純なアルゴリズムを紹介したいと思います。Epsilon-Greedy アルゴリズムです。これは、一定の確率で探索と活用を分ける手法になっており、例えば、定数epsilonを0.0~1.0の範囲で設定し、1 – epsilonの確率で活用、 epsilonの確率で探索を行なっていきます。この説明だけだとわかりにくいので、具体的な事例を挙げながら説明していきます。
Epsilon-Greedy アルゴリズムを試してみる
- テスト概要
広告配信を例に挙げましょう。まず前提として、今回は配信比率をA/Bテスト, Epsilon-Greedy アルゴリズムで比較しながら試したいと思います。テスト用の検証クリエイティブを5枚用意します。それぞれのクリエイティブはどのくらいCTRがあるのか、1クリックあたりどのくらいの報酬があるのかが、下記の通り、決まっているものとします。
そして、200万回の広告表示があった場合に、どのくらいのクリックがされて、売上(報酬金額)を上げられるかを比較したいと思います。この配信についての、クリエイティブ露出比率のコントロールをA/Bテスト, Epsilon-Greedy アルゴリズムでそれぞれ試したいと思います。まとめると、この検証を通じて、200万回の広告表示の中で、どういう最適化を行なえば、最も報酬金額を高められるかが分かるテストになってます。
- A/Bテストの検証方法
A/Bテストでは、200万回を2つに分けます。前半100万回は、ランダムでクリエイティブを表示し、最良の案件を選出します。そして、後半100万回は、全て最良の案件を表示するようにします。 -
バンディットアルゴリズムの検証方法
バンディットアルゴリズムでは、Epsilon-Greedy アルゴリズムを使い、活用:探索を8:2に設定して進めていきます。 -
実験
まず、A/Bテストです。前半100万回は、報酬金額が、2,640円になり、後半100万回は、報酬金額が、6,570円になりました。合計は、9,210円です。
一方で、バンディットアルゴリズムでは、探索と活用を行ない、報酬金額は合計10,016円になりました。
このように、探索と活用をしながら進めることで、A/Bテストより良い結果を出すことができました。
Epsilon-Greedy アルゴリズムが向いていないケース
検証では、A/Bテストよりも良い結果が出ましたが、万能ではありません。では、今回使ったEpsilon-Greedy アルゴリズムが向いていないケースはどのような場面でしょうか。
- 施行期間が短い場合/アクセス数が少ない場合は向いていない
探索と活用を並行して行なうので、サンプル数がA/Bテストを単純に行なうよりも多く必要になるため、短期間で最適なものを見つけ出すことに重点を置くのであればA/Bテスト(探索10:活用0) が向いています。(A/Bテストにおいてもサンプル数は重要だが、比較的少なくても成果が出やすいため)
また、長期的にサイクルを回していかないと常に探索と活用を行っているメリットは見出しにくいと考えています。
バンディットアルゴリズムから学べること
- トレードオフ、トレードオフ、トレードオフ
実世界でも探索と活用は必ずトレードオフになると思います。どこに落としどころを決めるかの妥協は必要です。
- デフォルトの設定には大きな意味がある
初期化に情報や文脈を用いることでスタートラインに大きな差が出ることがあります。仮説を立てたときの確認はしっかりと行なうことをおすすめします。
- リスクは取るもの
リスクがゼロなロジックはありません。全ての選択肢の値は少しでも知るべきですし、活かすも殺すもまず情報が必要だと思うので、最良の選択肢を選べるように情報のインプットを心がけましょう。