サイド観測付きバンディット問題における暗黙の探索による効率的学習

アブストラクト: 我々は、学習者に伝えられる情報が完全情報とバンディットフィードバックの間にある状況を捉える、部分観測性モデルの下でのオンライン学習問題を考察する。最も単純な変種では、学習者は自身の損失に加えて、いくつかの他の行動の損失も観測できると仮定する。明らかにされる損失は、学習者の行動と、環境によって選ばれる有向観測システムに依存する。この設定に対して、行動を選択する前に観測システムを知る必要がないにもかかわらず、ほぼ最適な後悔（regret）の保証を享受する最初のアルゴリズムを提案する。同様の流れで、学習者が受け取るフィードバックがセミバンディットと完全フィードバックの間にある、オンライン組合せ最適化問題をモデル化する新しい部分情報の設定も定義する。我々の最初のアルゴリズムの予測は、この設定では常に効率よく計算できないため、わずかに複雑な調整メカニズムを代償として、同様の性質を持ちつつ、常に計算効率が良いという利点を備えた別のアルゴリズムを提案する。両アルゴリズムは、implicit exploration（暗黙的探索）と呼ばれる新しい探索戦略に依拠しており、この問題に対してこれまで研究されてきた探索戦略よりも、計算面でも情報理論面でもより効率的であることが示される。