バンディット問題は動的意思決定を扱う最も基礎的な枠組みの一つです。 これは、事前には当たり確率が分からないスロットマシンが複数ある状況で、 当たり確率を逐次的に推定しながら次に選ぶスロットマシンを選ぶことで、 合計報酬の最大化や当たり確率最大のスロットマシンの発見を目指す問題です。

この問題は クリック率や購入率が未知のアイテムをユーザーに提示する推薦システムに広く用いられているほか 無線通信の帯域選択、農作物の作付条件の選択などさまざまな応用が考えられており、 1950年頃から既に研究が行われています。 これらに対し、確率論や統計学、最適化、情報理論などさまざまな手法を用いて 本質的な達成可能な限界を理論的に明らかにするとともに、 実用的なアルゴリズムを構築を行っています。

この問題では報酬が 一定の確率分布に従って生成される確率的設定、 敵対者がプレイヤーに損をさせるように報酬を決定する敵対的設定が主に知られており、 我々は主に確率的設定におけるアルゴリズムと理論構築を多く行っていました。 一方、これら両方の設定で最適オーダーの性能を達成する両環境最適方策というものが近年注目されており、 このような方策の構築にも近年は力を入れています。

実際の動的意思決定問題のうち単純なバンディット問題により定式化できるものはごく一部で、 選択可能な行動と得られる情報には複雑な関係をもつ場合が多いです。 例えば商品の価格付けの問題では、購買者がもつ商品の評価額が直接観測できず、提示額に対する購入の有無のみが観測されます。 このように多様な性質をもつ現実の問題を適切にモデル化することで 優れたアルゴリズムを構築することを目指しています。

強化学習はゲームAIやロボット制御など複雑な環境で優れた行動規則を獲得するために広く用いられており、 教科書にはよく「バンディット問題は強化学習の単純なタスクの一つ」という説明がされています。 一方実際には、バンディット問題の研究は比較的単純なタスクを扱うかわりに強い理論的保証を重視するのに対し、 強化学習の研究は理論的な保証が難しい複雑なタスクを実験的なアプローチにより取り組むものが多く、 ある種の棲み分けが存在しています。 そこで、新薬の治験など古典的には理論的アプローチによって多く取り組まれてきた問題に対して 強化学習を用いたアプローチを行うことで、理論と応用のギャップを埋めることを目指しています。