バンディットアルゴリズムまとめ

背景

継続的なテスト

• メリット：常に変化する環境の中で、最適な組み合わせを問うことができる。
  • はたしてハロウィーンの時のロゴとクリスマスの時のロゴが同じで果たしていいのか？
• デメリット：テスト期間は、ある程度収益を犠牲にすることになる。
  • 黄と紫の組み合わせのような、ひどいアイデアも出さなければならない（もちろん、結果的にわかるものだが）

探求と活用のトレードオフ

• 探求
  • 収益は犠牲になるかもしれないが、新しいアイデアを試す。
• 活用
  • 他にもっと良いアイデアがあるかもしれないが、現時点で最善のものを出す。

手法

概観

• 試したいアイデアをスロットマシンの腕とみなす。
  • 素晴らしい腕は、高い確率で収益をもたらす。
  • 事前知識はない。
• できるだけ少ない試行で優秀な腕を見つけ出し、得られる収益を最大にしたい。
• アルゴリズムのシステムの要素
  • 腕を引く
  • 学習する
• 外界とのインタラクションを通じて、報酬を最大化するエージェント。
• 学習する方法は基本的に加重平均
• 腕を引く方法について様々な手法が提案されている

シミュレーション

• 5 台の腕を用意する
• それぞれ 0.1, 0.1, 0.1, 0.1, 0.3 の確率で報酬 1 を得ることができる。
• それ以外は報酬 0

手法１：e-greedy

• 確率 e で「探求」を行う。確率 (1-e) で「活用」を行う。
• すなわち、確率 e でランダムに腕を選び、確率 (1-e) で今までの中最善とわかっている腕を選ぶ。
• 「何も考えずに、ある一定の確率でベンチ選手にチャンスを与える」

結果

• 探求する確率 e を大きくすればするほど、すぐに最適手が見つかるため、立ち上がりが早い。
• しかし、その後も懲りなく探求をし続けてしまうため、平衡状態に陥った後は e が小さい時に負けてしまう。

手法２：softmax

• 明らかに悪い腕についても、同じようにチャンスを与える必要があるのか？
• 惜しい腕には多めに、明らかに悪い腕には少なめにチャンスを与える方が、全体の収益を向上できるのではないか。
• そこで、温度パラメタ$T$を導入し、$n$個の腕のうち腕$i$が選ばれる確率$p_i$を以下のように定義する。 ただし、$v_i$は腕$i$によって得ることができる報酬の期待値。
• 「チャンスを与えた時の成績に応じて、起用を調整していく」

p_i = \frac{\exp(v_i / T)}{\sum_i\exp(v_i/T)}

• $T\to\inf$の時$p_i\to1/n$となり、ランダムに選択することに相当する。
• $T\to 0$の時、$p(argmax(v_i))\to1$

結果

• e-greedy よりも早く立ち上がるようになった。

手法２．５：アニールする softmax

• 温度をだんだんと下げていく
• 「ペナント後半になると、あまりスタメンを変えないようにする」

手法３：UCB

• ある腕に対する確信度合いを考えることで、たまたま否定的な経験を繰り返してしまったことで見誤るリスクを減らす。
• 確信度合いは、今までその腕をどれだけ試したかである。
• 「好奇心」項を導入して確信度合いが低いものを積極的に試していき、確信度高く成績の悪い腕を排除していく。
• 「新人は積極的に起用する」

結果

• まあまあの成績

まとめ

• 新しいアイデアを腕と見立てて、実験をしつつ収益を最大化するための手法について説明した。
• エージェントっぽい
  • ただ、自分で出す水準を操作するエージェントであり、出す因子を操作するエージェントではない。
• 後半の２つは、与えるパラメタが減るから良いという説明だったが、本当にそうかなと思った。
  • UCB だって、ボーナス項にパラメタがあるじゃん
  • アニール具合もパラメタじゃん
• スプリットテスト vs バンディットアルゴリズムというより、スプリットテストの戦略を考えるのがバンディットアルゴリズム。
• 複数変数がある場合は、その組み合わせを腕とする。

残る問題

• 普通、ウェブサイトで実験したいものは一つではない。
• ロゴだけではなく、テキストやフォント、色々なものを試したい。
• バンディットアルゴリズムでは、それぞれを組み合わせとして腕とすることを提唱しているが、実際はそれだけで組み合わせ爆発を起こしてしまう。
• 因子にも、確信度の概念を拡張することは出来ないか。
• 一つメタなバンディットアルゴリズムを作ることは出来ないか。

参考文献

• バンディットアルゴリズムによる最適化手法 John Myles White　著、福嶋雅子、株式会社トップスタジオ　訳 https://support.google.com/analytics/answer/2844870?hl=ja&ref_topic=2844866