確率的な意思決定集合と逆損失に対するオンライン組合せ最適化

Abstract

連続学習に関するほとんどの研究は、常に利用可能な、固定された一連の行動集合を前提としている。しかし実際には、行動は、センサーからの読取の部分集合を選ぶことから成り、時々失敗することがあり得る。道路区間は通行止めになる可能性があるし、商品が品切れになる可能性もある。本論文では、このような信頼性の低い複合行動における確率的な利用可能性の変動に対処できる学習アルゴリズムを研究する。さまざまな学習設定（学習者に与えられるフィードバックが異なる）に対して、Follow-The-Perturbed-Leader（摂動先行者追跡）予測手法に基づくアルゴリズムを提案し、解析する。提案手法は、Counting Asleep Times（眠っている時間を数える）と呼ぶ新しい損失推定技術に依存している。先行研究で扱われている、完全情報および（セミ）バンディット設定に対して、それぞれのアルゴリズムの後悔（regret）に関する上界を与える。さらに両者の自然な中間にあたる「restricted information（制限付き情報）設定」についても同様に扱う。特に注目すべき結果として、本成果は、確率的な利用可能性を伴う sleeping bandit（スリーピング・バンディット）問題に対する効率的なアルゴリズムによって達成される、これまでで最良の既知の性能保証が大幅に改善されることを示す。最後に、提案アルゴリズムを実験的に評価し、既知の手法に対する改善を示す。