K本腕バンディット問題と代表的なアルゴリズム

#はじめに
K本腕バンディット(n本腕バンディット、多腕バンディット)問題と呼ばれるタスクの説明及び代表的なアルゴリズムの解説記事です。
バンディット問題はシンプルな設定のため広告配信や治験など様々な応用例が挙げられる問題です。この記事でバンディット問題に興味を持ってくれた人はぜひ応用例について調べて見ると面白いと思います。

参考文献
バンディット問題の理論とアルゴリズム

#K本腕バンディット問題
K本腕バンディット問題とは、複数のスロット問題にも例えられるタスクで強化学習の中でも単純な問題と知られています。スロットにも例えられることから行動を腕、行動選択を引くと呼びます。(単純な問題とは言いましたが、単純=簡単な問題ではないので注意が必要)
強化学習とはエージェントと環境の相互作用により学習をおこなう手法のことを指し、K本腕バンディット問題も同様の枠組みで学習をおこないます。

しかし実は一般的な強化学習タスク(グリッドワールド,崖歩きタスクetc)と異なり、「状態が単一」や「遅延報酬がなく即時報酬のみ」など相違点がかなりあります。この違いから一般的な強化学習タスクよりかなりシンプルなタスク設定になり、強化学習で起こりうる問題が明確にみることができるため単純な問題と呼ばれます。
K本腕バンディット問題の目的は「限られたstepの中で最適な腕(行動)を発見しつつ、最終的に得られる累積報酬の最大化」をすることです。

#探索と活用のトレードオフ
K本腕バンディット問題では、上記の目的のため「探索」と「活用」をバランスよくおこなう必要があります。
探索とは、どの腕が最も報酬が得られる最適な腕か、今まであまり引いてこなかった腕を引いたりしながら探す行動です。一方活用は、学習していく中で見つけた最適だと思われる腕をひく行動です。
この2つをバランスよくおこなうことで最適な腕を発見しつつ累積報酬の最大化を目指すことができます。探索と活用は一回の行動選択でどちらか一方しか行えないことから探索と活用のトレードオフと呼ばれ、K本腕バンディット問題で最も重要な問題の1つとして考えられています。
#代表的なアルゴリズム
探索と活用のバランスをとるアルゴリズムとして以下のアルゴリズムが知られています。
どのアルゴリズムもそれぞれメリット・デメリットがあるため一概にこのアルゴリズムが良い・悪いと言うことは難しいです。タスクの設定によって使い分けたりするのが良いでしょう。
##ε-greedy
$0\leq\epsilon\leq1$ で任意の$\epsilon$ を設定し、
確率 $\epsilon$ で K 本の腕からランダムに腕を引く(探索)
確率 $1-\epsilon$ で K 本の腕の中から最適だと思われる腕を引く(活用)

• メリット
  • アルゴリズムの仕組みがシンプルなため実装が容易
  • $\epsilon$ をstepが経つごとに減衰させることで任意のstepで活用のみに切り替えることができる
• デメリット
  • 探索の時、割と良さそうな腕も明らかに悪そうな腕も等しく扱いランダムに選択してしまう

##softmax
ε-greedyのデメリットを改善しているのがsoftmaxです。各腕の報酬期待値を$\hat{\mu_i}$とした時、以下の式で各腕の選択確率$p_i$を計算します。

p_i = \frac{e^{\hat{\mu_i}/t}}{\sum_{i=1}^K e^{\hat{\mu_i}/t}}

tは温度パラメータと呼ばれるハイパーパラメータです。この温度パラメータが低いほど今までの結果を考慮した選択確率(活用)になり、高いほど今までの結果を考慮しないランダムな選択確率(探索)となります。

• メリット
  • 既知の情報を生かし、良さそうな腕ほど選択されやすい
• デメリット
  • 各腕の分散を考慮していない(50/100でも1/2でも同じように扱う)
  • 温度パラメータはかなり過敏なのでチューニングが難しい

##UCB1
分散(不確実性)を考慮できるのがUCB系のアルゴリズムです。今回はUCB系の中でもUCB1を紹介していきます。一般的にUCB系はUCBスコアと呼ばれるスコアの算出方法が異なるだけで、他は同じアルゴリズム群のことです。
以下の式がUCB1におけるUCBスコアの計算式です。このUCBスコアが最も大きい腕を引きます。
$t$は現時刻、$N_{t,i}$は時刻tまでにi番目の腕を引いた回数を表します。

a_t = \hat{\mu_i} + \sqrt{\frac{2 log(t)}{N_{t,i}}}

1項めは各腕の報酬期待値を表し、2項めは分散を考慮したボーナス項を表します。選択回数が少ない腕のボーナス項は式の定義上大きくなるため、報酬期待値が多少小さくても積極的に選ばれやすくなります。

• メリット
  • 報酬期待値＋分散を考慮し腕を選択できる
  • ハイパーパラメータがないためチューニングが必要ない
  • 試行回数が増えるに連れボーナス項は全体的に小さくなっていくため、報酬期待値に依存した選択(活用)に徐々に切り替えられる
• デメリット
  • どの腕もある程度の回数引くことになるので、悪い腕を探索のために引きすぎてしまう時がある
  • 決定論的なアルゴリズムでロバスト性に欠ける

##ThompsonSampling
ロバスト性をもつ確率論的なアルゴリズムで、報酬期待値が最大である確率と選択頻度を一致するような確率一致法のベイズ定式化です。
具体的な数式はややこしくなるので省きます。ざっくり流れを説明すると

1. 報酬のあたり回数や外れ回数をパラメータ更新に用いつつ各腕の事後分布を生成
2. この事後分布からサンプリングを行い、サンプリングした値が最大となる腕を引く

• メリット
  • 純粋に性能が良いアルゴリズム
  • 確率論的なのでバッチ処理等と組み合わせても安定した性能を発揮できる(ロバスト性)
• デメリット
  • 事後分布をいちいち生成するため他のアルゴリズムと比べ実行時間が長い
  • 数式まで理解しようと思うとかなり骨が折れる
  • 他のアルゴリズムは理論的保証があるが、このアルゴリズムはなかった(はず)

#おわりに
K本腕バンディット問題と代表的なアルゴリズムについて説明してきました。K本腕バンディット問題にも文脈付きバンディット問題や比較バンディット問題など仲間がいるので時間があったらそちらの解説もしたいと思います。