多腕バンディット問題を解説してPythonで実験してみた-ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

## 多腕バンディット問題とは

スロットマシーンで遊ぶことを考えます。
スロットマシーンがあなたの前にいくつかあることを考えましょう。(5ことか10ことか)

あなたは、決められた回数分(10000回とか)だけこのスロットマシーンをプレイすることができます。
スロットマシーンが当たる確率はスロットごとに異なります。
どのスロットも、当たれば1円儲かり、外れれば何ももらえません。

なので、当たる確率が一番高いスロットを決められた回数分ずーっとプレイし続けるのが一番儲かりますね。

しかし、問題があります。
あなたは、各スロットマシーンの当たる確率がわかりません。
いくつかスロットをプレイすることを通じて、当たりやすいスロットを見つけていくことが必要です。

ここで、これまで得られた結果から一番良さそうなスロットばかりプレイしていると、他のスロットの中にあるかもしれない一番当たりがでるスロットを見逃してしまいます。
逆に、一番良いスロットを探すために悪いスロットばかりプレイしてしまうのも、最終的な儲けが小さくなってしまいます。

多腕バンディット問題とは、この

* 最適なスロットを探すためにいろんなスロットをプレイしてみる(探索)
* これまでの結果から最適と思われるスロットをプレイする(活用)

のバランスをうまくとることができるアルゴリズムを提案して、最終的な報酬を大きくしようぜ、という問題です。
探索と活用という単語はこの分野で良く出てくるので、頭に入れて読んでもらえると嬉しいです。

また、このスロット一台一台のことをアームと呼びます。
アームは腕、ですね。なので多腕バンディット問題です。バンディットはスロット的な何かだったと思います。
今後はスロットではなくアームという単語を使っていきます。

## バンディット問題の種類と応用

バンディット問題は機械学習の分野で古くから研究されてきたテーマで、様々なタイプのものがあります。
その中でも一番基本的な、確率的バンディットを扱おうと思います。

確率的バンディットは、スロットマシーンの当たる確率が確率分布に従うものです。
時間によってこの分布が変わるタイプのものなどがありますが、ここでは基本的なものに絞って時不変な確率分布を扱っていきます。

仮定される確率分布はいろいろありますが、一番簡単なベルヌーイ分布を今回は仮定しましょう。

バンディット問題は実社会でも様々な応用があります。
web広告などが有名な例かと思います。

不確実な状況下で何かを選択しつつ、得られた情報をフィードバックして次の選択の参考にする、という構図は様々なところに見られるのではないでしょうか。

## アルゴリズム
バンディット問題を解く際に用いられるアルゴリズムの説明に入りましょう。
今回実験したアルゴリズムでだいたい基本的なものはカバーされていると思います。
bound証明などの数理的なアプローチは難しそうでわけわかめ〜ですが、アルゴリズム自体はとてもわかりやすい&実装もかんたんなものが多い印象です。

### ランダムにプレイ
これは遊びというか、ベースラインというか。
全てのアームの中から毎回ランダムに選んできてプレイします。

### ε-greedy

イメージとしては、コインを投げて表なら探索(最適なスロットを探すためにいろんなスロットをプレイしてみる)
裏なら活用(これまでの結果から最適と思われるスロットをプレイする)
をする、という方法です。

コインだと確率はどちらも0.5ですが、このε-greedyでは探索を行う確率をε、確率1-εで活用を行うようにします。
εはユーザーが勝手に決めてしまうハイパーパラメータです。

探索と活用では以下のような動作を行います。
割と自然。

探索 -> 全てのアームからランダムに引く
活用 -> これまでの報酬の平均が高いアームを引く(一度もひいてないのは0とみなす)

### softmax

ε-greedyの弱点として、「探索の際に良いアームも悪いアームも同じくらい探索してしまう」という点があります。

気持ちとしては、

「今は最適ではないけどそこそこ当たってはいる希望の持てるアーム」と、
「一回も当たっていない将来性のないアーム」

を同じくらい試してしまうという感じですかね。

その辺を修正したのがSoftmaxというアルゴリズムです。
softmaxはディープラーニングなどにも出てくるのでご存知の方も多いのではないでしょうか。

それぞれの腕のこれまでの報酬の平均$v_i$を計算するところまでは一緒。
得られた確率の列をsoftmax関数にかけ、得られた確率分布$p_i$にしたがって次の一手をサンプリングする
$p_i$は、i番目のアームを選ぶ確率を表します。

$p_i=\frac{\exp (\frac{v_i}{T})}{\sum \exp (\frac{v_i}{T})}$

$T$はハイパーパラメータ。
Tが大きいほどランダムに近い選び方(これまでの結果を考慮しない)になり、
Tが0に近いほどこれまでの報酬の平均$v_i$を重視して次の手を選ぶようになります。

$v_i$のままだとiについての和が1にならないので、softmax関数をかけてそれ自体を確率分布にしてあげようという気持ちです。

### UCB方策(Upper Confidence Bound)

他にも改良すべき点があります。
それは、「アームを試した回数を考慮していない」という点です。

すなわち、これまでのアルゴリズムでは各アームのこれまでの当選確率のみを計算して用いていただけなので、
「100回試して1回も当たらなかったアーム」
「1回試したが当たらなかったアーム」

が同様の評価になってしまいます。
どう考えても上のアームは悪いアームの気がしますし、下のアームはまだまだチャンスを与えても良い気がします。

UCBではこれを改良します。
すなわち、「試した回数が少ないものほど積極的に試す」ようになります。

アルゴリズムは以下の通り。
これまでと同様に、各アームのこれまでの報酬の平均を計算した後、探索の必要性の項(bonus項)を追加します。

i番目のアームのスコアは以下のように計算します。
$UCB_i=\mu_i + \sqrt(\frac{\log t}{2T_i})$
$\mu_i$はi番目のアームのこれまでの報酬の平均。
tは全体のプレイ回数。
$T_i$はこれまでにi番目のアームを使用した回数。

このUCBスコアが一番大きいアームをプレイするのがUCBアルゴリズムです。
bonus項は試行回数が小さいアームほど大きくなるので、意図した改良が実現できているのがわかるかと思います。

一番最初は$T_i$がどのアームも0だからzero-divisionになるんじゃね？と思ったけど、実装では最初は全てのアームを一回ずつ引いてから、このスコアを計算するという方法で行うみたいです。

いろんな記事を読んでみたのですが、bonus項が記事によって異なっていて混乱しました。
bonus項として
$\sqrt(\frac{\log t}{2T_i})$
と
$\sqrt(\frac{2\log t}{T_i})$
の記事や、その部分の定数はなんでもいいよっていうのもあって不思議でした。

2が分母にくるやつが一番しっくりくるし、数式からの導出があったのもこれだけだったので今回はそれを採用しました。

### Thompson Sampling
このThompson Samplingが何を改良したのかがあんまりちゃんと理解できていないのですが、
このアルゴリズムは強いです笑

ベイズをつかう手法。
各アームのパラメータはそれぞれの事前分布によって生成されると仮定して、ベイズの公式を用いて事後分布を計算してベストなアームを選択する手法です。
もちろんそれぞれの事前分布は試行を行うごとに更新していきます。

ベイズの細かい計算は省略しますが、元の分布がベルヌーイ分布でそのパラメータの事前分布をベータ分布とすると、
事後分布もベータ分布になる、という特性があります。共役事前分布ってやつですね。

ベイズの公式(事後分布∝事前分布x尤度)からすぐ確認できますので気になったら試してみてください。

ということで、
それぞれのアームがベルヌーイ分布の時、事前分布をベータ分布と仮定すると事後分布もベータ分布になるわけですから、事後分布の計算はβ分布のパラメータを更新していくだけで良くなります。かんたん。(というか簡単になるようにβ分布を選んだだけですが)

アームのパラメータの事後分布を$B(a,b)$とおいて(B(a,b)はβ分布)
少し計算すると、
「アームが当たったら$a$に1追加,外れたら$b$に1を加える」という更新式が得られるので、
最初の事前分布をB(1,1)(すなわち一様分布)で初期化すると、事後分布の計算は以下のようになります。

当たった回数と外れた回数を各アームについて記録しておき、これらを$(a_i,b_i)$とします。
このとき、β分布$B(a_{i+1},b_{i+1})$がアームiのパラメータの事後分布になります。
なので、事後分布を計算するといっても、実際は各アームの当たった回数と外れた回数を記録しておけばいいだけ！

得られた各アームのパラメータの事後分布から、ベストなアームを決める部分は、
単純に各アームがベストなアームである確率を計算するのは困難なので、サンプリングを行います。

具体的には、各アームのパラメータの事後分布から乱数を発生させて、最大の乱数を吐きだしたアームを選びます。
これでもちゃんとした近似になるみたいです。考えた人あたまいい〜

## 実験
実験しました。
Python3で実装しています。

確率的な挙動なので、モンテカルロシミュレーションを用いて実験しました。
10000回プレイを500回行い、その平均を各アルゴリズムの性能としています。

実験は3つ行いました。
* ε-greedyのεを変えて比較(0.1,0.2,0.3,0.4,0.5)
* softmaxのTを変えて比較(0.01,0.05,0.1,0.3,0.5)
* 各アルゴリズムを比較

どの実験もアームは10本使用しています。
各アームのあたり率は以下のようになっています。

|アーム1|アーム2|アーム3|アーム4|アーム5|アーム6|アーム7|アーム8|アーム9|アーム10|
|----|----|----|----|----|----|----|----|----|----|
|0.1|0.1|0.2|0.2|0.3|0.3|0.4|0.4|0.5|0.6|

アーム10ばかりプレイ出来ればいいアルゴリズムということになりますね。

## 結果

まずはε-greedyのεを変えて比較する実験。
各時刻において最適なアームを選択できている割合のグラフと、最終的にどれだけ報酬が得られたかを表すグラフが以下になります。

ε=0.1の場合が一番最終的に最適なアームを選べていて、報酬も一番得られていることがわかります。
10回に1回ぐらいは最適じゃないような選択肢を試してみるのもいいよっていう結果ですね。
いそがばまわれ。

次に、softmaxのTを変えて実験。
同じ種類のグラフを貼ります。

Tとしては0.05が一番良さそうです。

ハイパーパラメータについては、他にアニーリングという手法があります。
ゲームの終盤になるにつれて探索より活用を重視するようにハイパーパラメータを変化させていく手法です。
ε-greedyのεやsoftmaxのTを小さくしていき活用を重視するように調整していくわけですね。

また今度試してみようと思います。

最後に、これまで見つけたベストなハイパーパラメータを使って各アルゴリズム同士を比較します。

softmaxがε-greedyに負けているのが悔しいですが、それ以外は概ね正しそうな結果です。

## おわりに

修士の研究内容をどうしようか考えている時にバンディットに出会いました。
そこそこ調べたのもあって実装してみたくなり、今回の記事に至りました。

データもいらないし実験しやすいと思うので、気になった方は試してみるとたのしいかもしれません。

読んでくださってありがとうございました。

## ソースコード
githubリポジトリを貼っておきます。
(アームが多くなると計算が重くなるだめだめアルゴリズムなので本当はなおしたい)

<a href="https://github.com/habroptilus/bandit">https://github.com/habroptilus/bandit</a>

## 参考

<a href="https://www.amazon.co.jp/Bandit-Algorithms-Website-Optimization-Developing-ebook/dp/B00AM86Y0K">Bandit Algorithms for Website Optimization: Developing, Deploying, and Debugging</a>

これ英語ですけど、割と読みやすいし基本的なアルゴリズムが網羅されているのでよかった。

多腕バンディット問題を解説してPythonで実験してみた

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT