バンディット問題における強制探索

多腕バンディット（MAB）は古典的な順次決定問題です。ほとんどの研究は報酬分布についての仮定（例：有界）を必要としますが、実務者は非定常MAB問題においてこれらの分布についての情報を取得するのが難しいことがあります。本論文では、報酬分布に関する情報を使用せずに実装でき、かつ相当な後悔上限を達成できる多腕バンディットアルゴリズムの設計を目指します。そのために、貪欲なルールと強制探索を交互に用いる新しいアルゴリズムを提案します。我々の手法はガウス分布、ベルヌーイ分布および他のサブガウス分布に適用でき、その実装は追加情報を必要としません。異なる強制探索戦略に対して統一的な分析手法を用い、定常および区分的定常設定における問題依存の後悔上限を提供します。さらに、我々のアルゴリズムを異なる報酬分布における人気のバンディットアルゴリズムと比較します。