Bandit Algorithm のバックアップ(No.4)

基本的なバンディットアルゴリズム

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

定義

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

例

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

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

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

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

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

問題の拡張には

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

各種のバンディットアルゴリズム

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

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

＜以降、後日執筆＞