はじめに
「複数の選択肢からできるだけ最適なものを選択したい」というような問題設定は世の中にありふれています。例えば、広告Aと広告Bのどちらが効果的にクリック数を稼ぐことができるのかだったり、新薬Aと新薬Bのどちらがある病気を効果的に治癒するのかだったりというような状況です。このような問題が難しいのは、最適な選択をできるだけ多く取りたいという活用と最適な選択が何であるかをできるだけ正確に知りたいという探索のトレードオフがあるからです。つまり、できるだけ多く広告Aと広告Bの優れている方を用いてマーケティングを活用したいというモチベーションと、広告Aと広告Bのどちらが優れているのかを正確に知りたいという探索のモチベーションが混在するのです。
これらの状況において最適な介入を選択するためによく用いられるのは、A/BテストやRCTと呼ばれる手法です。それは、AとBの二つの介入を被験者にランダムに割り当ててどちらの介入が平均的に優れているのかを統計的仮説検定に基づいて選択します。
しかしこの典型的なA/Bテストには大きな懸念点があります。それは、純粋な探索を一定期間行ってから純粋な活用を行うというその性質上、純粋な探索期間に無駄な探索をしてしまう可能性や純粋な活用の期間に誤った活用をしてしまう可能性があるのです。
今回は、それまでの介入により得られた実験結果から次の施策を決めることにより、活用と探索をバランスよく織り交ぜて全体の累積的な報酬（広告の例で言うならばクリック数）を最大化することを目指すバンディットアルゴリズムを概観します。
今回使用したコードはこちらからご覧になれます。
目次
バンディットアルゴリズムの定式化
先ほど、「探索と活用のジレンマ」を紹介しました。つまり、限られた実験回数の中で、現在持っている情報から導かれる最適な選択肢を選ぶ活用という考え方と現在知っている情報以外の情報を獲得して今後の意思決定に生かそうとする探索考え方の間に起こるトレードオフのことです。もし、活用ばかりを行ってしまうと実は最適だった選択肢に気づかず、自分が知っている情報から導かれた誤った選択肢を多く選んでしまうことになります。一方で探索ばかりをしてしまうと、良い選択肢がすでにわかっているにも関わらずそれを十分に選ばないことにより結果的に良くない選択肢を多く選んでしまうことになります。そして、例えば、農作物に適切な農薬が何であるかを調べたいときなど限られた回数しか実験できない状況においてはなおのこと難しい問題と言えます。
そのような状況において威力を発揮するのが探索と活用を効率的に織り交ぜることにより一定期間における報酬を最大化するためのアルゴリズムであるバンディットアルゴリズムです。バンディットアルゴリズムでは、それまでの実験結果を用いて次にどの選択肢を取るかを逐一決めて行きます。そうして探索と活用をある基準に基づいてうまく織り交ぜることによって最終的な報酬を最大化することを目指します。バンディット問題は以下のような定式化の種類があります。
（注）以降では、これまで選択肢や介入としてきたものを$腕$と表現します。これは多腕バンディット問題が元々複数のスロットマシンをプレイするギャンブラーのモデル（どのスロットのアームを引くべきであるかを定式化した。）に端を発することからきています。
Notation
以下の説明に用いる記号を整理します。
| 記号 | 意味 |
|---|---|
| $K$ | 腕の集合 |
| $T$ | 総試行回数 |
| $t$ | （ある時点までの）試行回数 |
| $t_k$ | （ある時点までの）腕$k$の試行回数 |
| $a_t , (\in K)$ | $t$において選択する腕 （t-1回の試行による情報からアルゴリズムが決定） |
| $x_{ a_t }^t$ | t回目の試行で選択される腕 $a_t$ から得られる報酬 |
| $\mu_k$ | 各腕$k$から得られる報酬の真の期待値 |
| $\hat{\mu_k}$ | 腕$k$から得られる報酬の期待値の推定値 その時点までの腕$k$から得られた報酬の標本平均 |
###定式化の種類
バンディット問題には大きく以下の定式化が存在するようです。今回は、最もベーシック（？）な確率的定式化の基礎について勉強してみました。確率的定式化では、各腕$k$から得られる報酬が期待値$\mu_k$のベルヌーイ分布に従うとして腕に関する事前情報がない状態から総試行回数$T$後の期待報酬を最大化することを目指します。
その他の定式化については今後動向を追ってみたいと考えています。
| ベイズ的定式化 | 確率的定式化 | 敵対的定式化 | |
|---|---|---|---|
| 腕 | マルコフ決定過程 | 確率分布 | 任意（敵が不利な報酬を設定してくる） |
| 目的 | 事前分布のもとで期待報酬最大化 | 期待報酬最大化 | 敵に対する報酬の最大化 |
| 代表的なアルゴリズム | Gittins指数 | ε-greedy, UCB, TS | Exp3 |
#代表的なバンディットアルゴリズム
ε-greedy
バンディットアルゴリズムの中でも最もシンプルなのがε-greedyと呼ばれるアルゴリズムです。このアルゴリズムでは、$\epsilon$の確率で探索を行い、$1-\epsilon$ の確率で活用を行います。つまり、以下のように探索する腕が決まります。
- 探索フェーズ（確率$\epsilon$）: 全ての腕の中からランダムに選択
- 活用フェーズ（確率$1-\epsilon$）: それまでの実験結果をもとに最も良い腕（報酬の標本平均が最大のもの）を選択
ε-greedyアルゴリズムには以下のようなメリットとデメリットがあると言われています。
-
メリット
- アルゴリズムの仕組みがシンプル
-
デメリット
- 常に確率$\epsilon$で腕の探索を行ってしまう。
- 全ての選択肢を等しく評価してランダムに探索する選択肢を選んでしまう（既知の情報が全く使用されない。）
- ハイパーパラメータの値によって性能が変わってしまう。
Softmax
ε-greedyのデメリットである全ての選択肢を等しく評価して探索してしまうという点を修正したのがSoftmaxアルゴリズムになります。Softmaxアルゴリズムでは、以下の式によりそれぞれの腕を探索する確率$p_k$決めることでそれぞれの腕に対する既知の情報を踏まえた探索を目指します。
（$\tau$はSoftmaxアルゴリズム固有のハイパーパラメータです。）
p_k = \quad \frac{e^{\hat{\mu_k}/\tau}}{\sum_{i=1}^ne^{\hat{\mu_i}/\tau}}
Softmaxアルゴリズムには以下のようなメリットとデメリットがあると言われています。
-
メリット
- 既知の情報を生かして良さそうな腕ほど探索されやすい。（既知の情報を使用する。）
-
デメリット
- 選択肢の分散を考慮していない。
（例えば100回選んで50回当たりが出た選択肢と2回選んで1回当たりが出た選択肢を同程度に評価してしまいます。） - ハイパーパラメータの値によって性能が変わってしまう。
- 選択肢の分散を考慮していない。
(補足) 試行回数が多くなるにつれてハイパーパラメータである$\tau$を小さくすることにより試行回数が少ないときはよりランダムに探索し、試行回数が多くなるにつれて確実に既知情報により良いとされる選択肢を選ぶように修正することも可能です。（これをアニールすると呼びます。）
UCB1
Softmaxのデメリットであるそれまでの腕の既知情報に関して分散を考慮しないというデメリットを解消したアルゴリズムがUCB(Upper Confidence Bound)1と呼ばれるアルゴリズムです。UCB1アルゴリズムでは以下のような式により探索する腕を決めることで腕に関する既知の情報として平均的な良さ（報酬の平均値）だけではなくて分散も考慮します。
a_t = \arg \max_k \quad \hat{\mu_k} + \sqrt{\frac{2\log(t)}{t_k}}
UCB1アルゴリズムには以下のようなメリットとデメリットがあると言われています。
-
メリット
- 既知の情報から推定される腕の良さだけではなくてどの程度その腕に関して知っているかを考慮した上で探索する腕を決める。
- ハイパーパラメータを設定する必要がない。
- 試行回数が増えるにつれて徐々にそれまでの情報から推定される最も良い腕を活用するように収束する。
-
デメリット
- 悪い腕を探索のために選択し過ぎてしまうことがある。
（補足）
UCB1アルゴリズムでは、その名（Upper Confidence Bound）の通り各腕の報酬の期待値の上側信頼区間が最大になる腕を各試行回で選択していきます。ここで各腕について各試行回数$t$から得られる報酬$x_k^i$は独立なベルヌーイ分布から得られるとして、$\hat{\mu_k^{ t_k }}$をそれまでの試行回数$t_k$における腕$k$から得られた報酬の標本平均とします。このとき、Hoeffdingの不等式より以下の関係が成り立ちます。
$$ P , \bigl(, \mu_k > \hat{\mu_k^{ t_k }} + u ,\bigr) \leqq \exp(-2t_ku^2) $$
ここで、右辺を$\delta$とすると、
$$ P , \Bigl(, \mu_k > \hat{\mu_k^{ t_k }} + \sqrt\frac{2\log(\frac{1}{\delta})}{t_k} ,\Bigr) \leqq \delta$$
つまり、$\hat{\mu_k^t} + \sqrt\frac{2\log(\frac{1}{\delta})}{t_k}$は腕$k$の報酬の期待値の上側1-$\delta$信頼区間ということになります。ここで、$\delta = \frac{1}{t}$とすると、UCB1のアルゴリズムとして紹介した式が出てきます。つまり、UCB1アルゴリズムでは、各試行回数$t$においては、報酬の期待値の上側$1 - \frac{1}{t-1}$信頼区間が最大となるような腕$a_k$を選ぶようなアルゴリズムになっているのです。（試行回数が多くなるにつれ単純な活用に近づいていきますね。）
ちなみに、UCB1アルゴリズムの$\hat{\mu_k^{ t_k }}$ の部分は単純にそれまでの報酬の標本平均が大きいを腕を活用する様子を、 $\sqrt\frac{2\log(t)}{t_k}$の部分は、腕$k$の試行回数が少ないほど大きな値となることから情報が少ない腕を探索する様子を表していると言えます。
シミュレーション
これまでに紹介した3つの基本的なアルゴリズムの性能をシミュレーションによって評価・比較してみます。
シミュレーションは以下のように行いました。
- 腕
- アタリの場合の報酬が1, ハズレの場合の報酬が0である5つの腕
- それぞれの腕はそれぞれ、アタリの確率が10%, 30%, 50%, 70%, 90%のベルヌーイ分布に従う。
- （一回のシミュレーションにおける）試行回数
- 1000回
- シミュレーション回数
- 1000回
- 評価指標
-
- 各試行回数における報酬の平均（早く最適な腕を見つける性能を評価）
-
- 各試行回数までの累積報酬（500回の試行において全体的な報酬を最大化する性能を評価）
-
- 比較アルゴリズム
- ε-greedy ($\epsilon = 0.2$)
- ε-greedy ($\epsilon = 0.5$)
- Softmax ($\tau = 0.2$)
- Softmax ($\tau = 0.5$)
- UCB1
まずは、各試行回数における報酬の平均を描画してみます。
これを見ると試行回数が少ない状況ではε-greedy($\epsilon = 0.2$)が早く良い腕を見つけているように見えますがその後試行回数が増えるにつれてUCB1が高確率で良い腕を引いています。UCB1のメリットである試行回数が増えるにつれてより良い腕を引くという活用に収束していく様子が見て取れます。ε-greedy($\epsilon = 0.5$)は試行回数が50回くらいまでは、ε-greedy($\epsilon = 0.2$)やUCB1と同程度の性能を見せていますが、その後伸び悩んでいることからも良くない腕を探索しすぎている様子が伺えます。
| アルゴリズム | 最終的な報酬の平均 |
|---|---|
| ε-greedy ($\epsilon = 0.2$) | 0.833 |
| ε-greedy ($\epsilon = 0.5$) | 0.685 |
| Softmax ($\tau = 0.2$) | 0.586 |
| Softmax ($\tau = 0.5$) | 0.592 |
| UCB1 | 0.858 |
次に、各試行回数までの累積報酬（1000回のシミュレーションにおける平均）を描画してみます。
これを見るとUCB1とε-greedy($\epsilon = 0.2$)が良い性能を示しています。上述したようにε-greedy($\epsilon = 0.5$) はそれぞれハイパーパラメータの設定値が大きすぎて探索が余分に多くなってしまい、結果的に良くない腕を引きすぎたため試行回数が多くなるにつれて上位のアルゴリズムから差をつけられた結果となりました。また、今回の設定ではSoftMaxアルゴリズムは共に振るわない結果となっています。もしかしたら問題設定に対して適当なハイパーパラメータの値とは大きく異なる値を設定してしまっていたのかもしれません。
| アルゴリズム | 累積報酬の平均 |
|---|---|
| ε-greedy ($\epsilon = 0.2$) | 809.089 |
| ε-greedy ($\epsilon = 0.5$) | 696.520 |
| Softmax ($\tau = 0.2$) | 577.353 |
| Softmax ($\tau = 0.5$) | 578.273 |
| UCB1 | 827.100 |
さいごに
今回の基本編では、代表的なアルゴリズムを3つ紹介してシミュレーションによって最適な腕を見つける性能と限られた試行回数において累積報酬を最大化する性能を評価・比較しました。しかし、シミュレーションの設定（アタリ確率のオーダーや試行回数、ハイパーパラメータなど）によってはアルゴリズムの性能は大きく変わると考えられるため皆さんも一度試してみると良いと思います。
今後は、バンディットアルゴリズムの一つであるTompson Samplingを紹介したり、Contexitual Banditと呼ばれる文脈を考慮したバンディットの定式化について書いていこうと思います。