Bandit Algorithm

バンディット問題

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

定義

多腕バンディット問題 (Multi-armed Bandit problem) とは、『複数の選択肢があり、選択肢が選ぶと報酬が得られる環境において、限られた回数だけ選択できるという条件のもと、得られる報酬を最大化する。ただし、選択肢から幾らの報酬が得られるかは、選ぶまで不明である。』という問題である。
この問題を解決するアルゴリズムをバンディットアルゴリズム (Bandit algorithm)と呼ぶ。

報酬の分布により、

• 確率的バンディット問題 (stochastic bandit)
• 敵対的バンディット問題 (adversarial bandit)
  等に分かれる。

例

よく使われる例えとして、N個のスロットマシンが使われる。

• スロットマシンの腕 (arm) を引くと、報酬を得られる。
  • スロットマシンによって得られる報酬が異なる。
    • ただし、腕を引いてみるまで報酬は不明。
• スロットマシンを引ける回数はK回。

強化学習的側面から見た定義

状態の集合：\( S=\{s\} \)
行動の集合：\( A=\{a_1,\dots,a_n\} \)
報酬関数：\( R:A \to \mathbb{R} \)
ただし、遷移関数は無い（\( s \to s \)の状態遷移しかない）
と整理できる。
つまり、強化学習問題モデルの一種として使われる有限マルコフ決定過程の部分問題として見なすことができる。
状態が一つしかないため、に単一状態マルコフ決定過程と言うこともできる。

他の問題・アルゴリズムとの関係

問題の拡張には

• linear bandit
• 文脈付きバンディット問題 (Contextual Bandit)
  などがある。

問題解決のアプローチ：探索と活用

バンディット問題では、報酬の高い選択肢を選択したい（活用）が、一方で、未知の選択肢を選択（探索）しなければ、より高い報酬を得られる選択肢を逃すかもしれないという問題がある。
この探索と活用のトレードオフを解決するため、幾つかのアルゴリズムが提案されている。

確率的バンディット問題 (stochastic bandit)

得られる報酬がそれぞれ別々の確率分布に従っているとするバンディット問題。

＜以降、後日執筆＞

リンク

• Finite-time Analysis of the Multiarmed Bandit Problem
  Peter Auer, Nicolò Cesa-Bianchi & Paul Fischer
  Machine Learning 47, 235–256 (2002)

• Vol.31.No.5(2016/9)多腕バンディット問題
  日本人工知能学会

• 強化学習その1
  西尾泰和