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

k本腕バンディット問題の定義

バンディットアルゴリズムが扱うのは、k本腕バンディット問題と呼ばれる問題です。k個の選択肢(行動)があり、その中から1つを選ぶことを繰り返します。行動を1つ選ぶたびに、数値の報酬を1つ受け取ります。この報酬は、選んだ行動によって決まる確率分布に従って出てきます。この確率分布は時間がたっても変わらない、定常なものとされています。

目指すのは報酬の合計の期待値

この問題の目的は、ある期間にわたって受け取る報酬の合計の期待値を最大にすることです。期間の例としては、行動の選択を1000回行うといった設定が挙げられます。1回ごとの報酬ではなく、決められた回数の選択を通した合計で良し悪しを測る点が特徴です。

評価的フィードバックという性質

強化学習で受け取るフィードバックは評価的なものです。評価的フィードバックとは、取った行動がどれだけ良かったかを示すだけで、その行動が最善だったかどうかは示さないフィードバックのことです。

このため、選ばなかった行動がどれだけ良かったかは、その行動の報酬からは分かりません。ある行動の良さを知るには、その行動を実際に選んで報酬を受け取る必要があります。いま良さそうに見える行動だけを選び続けると、まだ試していない行動や試した回数の少ない行動の良さは分からないままになります。

複数の状況にまたがらない単純化された設定

k本腕バンディット問題は、複数の状況にまたがらない問題です。状況によって最善の行動が変わるという要素を取り除き、行動を選んで報酬を受け取ることの繰り返しだけを残しています。そのため、評価的フィードバックのもとで行動をどう選ぶかという強化学習の基本的な問題を、単純化された形で学ぶための題材になっています。

代表的な解法との関係

この問題で行動をどう選ぶかを決める具体的な方法として、ε-greedy方策やUCB方策があります。それぞれの仕組みは、ε-greedy方策とUCB方策の項目で扱います。