オンライン最適化入門

社員を増やすかアルバイトで凌ぐかどちらがよいか。ベンチャービジネス売却の最適タイミングはいつか。 顧客にダイレクトメールを送る際の件名はどの候補にするか…。将来に関する選択を迫られるとき、最善と信じた選択が後悔を産むことは世の常です。本講演では、このような未知の将来に関する最適化であるオンライン最適化について概観します。 　まず、後悔の大きさの指標である競合比とリグレットについて紹介し、最適な選択方法とはどのようなものであるかについて単純な例を用いて解説します。そして、オンライン最適化の重要なトピックとして、探索と活用のバランスの取り方と、特定の行動をとる最適なタイミングの見つけ方について解説をいたします。

1. オンライン最適化の基礎
   1. オフライン最適化とオンライン最適化
   2. オンライン最適化の分類
2. 競合比解析
   1. 競合比の定義
   2. スキーレンタル問題と最適アルゴリズム
   3. 確率的方法による改善
3. リグレット解析
   1. リグレットの定義
   2. エキスパート統合問題と最適アルゴリズム
   3. オンライン学習
4. 探索と活用
   1. 探索と活用のトレードオフ
   2. 多腕バンディット問題
   3. 最適腕識別とA/Bテスト
5. 最適停止タイミング
   1. 秘書問題
   2. 預言者の不等式