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

バンディットアルゴリズムは、どれが当たりかわからない選択肢を試しながら選び続け、報酬の合計をできるだけ大きくする方法です。名前は、スロットマシンの俗称「one-armed bandit（片腕の盗賊）」に由来します。腕（レバー）が何本もあるスロットマシンで、限られた回数でどの腕を引くかを考える問題を、多腕バンディット問題と呼びます。

探索と活用のジレンマ

各腕の当たりやすさは、引いてみないとわかりません。これまでで最も成績のよい腕を引くのが活用、まだよく知らない腕を試すのが探索です。活用ばかりでは、一番よい腕を見落とすおそれがあります。探索ばかりでは、報酬を稼げません。この釣り合いをどうとるかが中心の課題です。

最良の腕を毎回引いた場合と比べて取り逃した報酬の合計をリグレットと呼び、性能の指標にします。

代表的な方法

• ε-greedy方策：確率εで腕を無作為に選び、それ以外は平均報酬が最大の腕を選びます。
• UCB方策：平均報酬に、試した回数が少ない腕ほど大きくなる上乗せを加え、その合計が最大の腕を選びます。
• トンプソンサンプリング：各腕が最良である確率に応じて腕を選びます。

強化学習との関係

バンディット問題は、どの腕を引いても状況（状態）が変わらない、最も単純な強化学習の問題とみなせます。行動が次の状態を変えるマルコフ決定過程から、探索と活用の問題だけを取り出した形です。

ビジネスでの使い道

広告やデザイン案の選択、商品の推薦などに使われます。A/Bテストでは、決めた期間は各案を均等に表示し、その後で勝者を決めます。バンディットアルゴリズムは、成績のよい案へ表示を寄せながら比べるので、テスト中の機会損失を抑えやすくなります。利用者の属性などを手がかりに選ぶ文脈付きバンディットもあり、ニュース推薦に応用した2010年の研究では、文脈を使わない手法よりクリック率が12.5%改善したと報告されています。