他腕バンディットアルゴリズムの概要と実装

多椀バンディットアルゴリズムとは、 探索と活用を効率的におこない、 一定期間の利益を最大化するアルゴリズム。

たとえば、

確率分布がことなるスロットマシンが複数台あったとき、 全部をまずは試してみないとどの台がベストかはわからないけれど、 とりあえず出にくい台に割く時間は少なくしたいよね、

みたいな場合。

epsilon-greedy

期待値の最も高いスロットを選ぶ。 100回中99回当たったスロットより、1回中1回当たったスロットを選ぶ。

期待値がわからない場合、すべてのスロットからランダムに選んでプレイ。

用語

  • 活用:これまでの期待値を活用して、最も良いスロットを選んでプレイ

  • 探索:ランダムにスロットを選んでプレイ

メリット

  • シンプルなしくみで実装が楽ちん

デメリット

  • 試行回数を考慮しないため、1000回中50回当たることも2回中1回当たることも同等に評価してしまう。
  • 探索がどれほど進んでも、既に獲得された知識だけですすめる方向(活用)のみに切り替えることはせず、予め決めたパラメータの割合でランダムにスロットを選ぶ行為(探索)が発生する
  • 上記により、さんざん試行した結果、「全然出ない台」とわかっている台も、探索のさいにはランダムに選択してしまう

---> 活用の割合を徐々に1に近づけていく改良を行うことで改良。

  • 活用シーンで最も良いスロットを使い続けるので、最初に実際はよく出る台が良くない結果を出し続けた場合、活用しなくなるので、あとで修正して良いスロットだと判断するのに時間がかかる

ABテスト

ある一定の期間は探索のみを行う。その後、わかった結果から、活用のみを行う。

探索シーンでは、すべてのスロットをランダムに使う。

活用シーンでは、期待値の最も高かったスロットを使い続ける。

メリット

  • スロットが2台のとき、非常に効率がいい
  • 活用シーンに入れば、計算がいらない(利用結果ごとにスロットの評価を行わなくていい)

デメリット

  • 探索で、効率の悪いスロットもいいスロットも同様に利用する

softmax

当たった確立の加重平均でそのスロットを使うことで、

当たる確率の高いスロットを高確率で、当たる確率のひくいスロットを低確率でひいて活用と探索をおこなう。

Upper Confidence Bounds

あるスロットについてどれだけ試したかも考慮に入れて、スロットをえらぶ。

実装例

あとで書く

参考

www.slideshare.net